bpp (1289B)
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 known that [PTIME] is included in BPP; the converse implication is not known 6 7 it is not known if BPP is contained in [nptime] 8 9 It is known that if [nptime] subseteq BPP then in fact [nptime] = [rp] : if you have an 10 efficient algorithm for a NP problem that errs in both directions, then in fact 11 you can remove errors on one side (uses [self_reducibility]) 12 13 [sipser_lautemann_theorem]: It is known that BPP is in [sigma2_cap_pi2]: https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem 14 - as BPP is closed under [complementation] it suffices to show that it is in [sigma2] 15 16 Analogue [BPL] with logarithmic space condition 17 18 Corresponding notion of [algorithm] running in [ptime]: "[monte_carlo_algorithm] with bounded probability of two-sided error" 19 20 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) 21 - cf [isolated_cut_point] 22 23 Up: [complexity_random] 24 25 See also: [rp], [automaton_monte_carlo_two_sided], [monte_carlo_algorithm]