bpp (1209B)
1 # BPP 2 3 Class BPP: [algorithm_randomized] for [decision_problem] with [two_sided_error] can err in both directions with proba 1/4. The error probability can be made exponentially small by retrying 4 5 it is not known if BPP is contained in [nptime] 6 7 It is known that if [nptime] subseteq BPP then in fact [nptime] = [rp] : if you have an 8 efficient algorithm for a NP problem that errs in both directions, then in fact 9 you can remove errors on one side (uses [self_reducibility]) 10 11 [sipser_lautemann_theorem]: It is known that BPP is in [sigma2_cap_pi2]: https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem 12 - as BPP is closed under [complementation] it suffices to show that it is in [sigma2] 13 14 Analogue [bpl] BPL with logarithmic space condition 15 16 Corresponding notion of [algorithm] running in [ptime]: "[monte_carlo_algorithm] with bounded probability of two-sided error" 17 18 Generalization [pp], with [two_sided_error] and there is no constant bound on how the probability differs in the case of a YES instance and of a NO instance https://en.wikipedia.org/wiki/PP_(complexity) 19 - cf [isolated_cut_point] 20 21 Up: [complexity_random] 22 23 See also: [rp], [automaton_monte_carlo_two_sided], [monte_carlo_algorithm]