BPP (complexity class)

In complexity theory is BPP ( Engl. Bounded error probabilistic polynomial time ) for a complexity class of decision problems . A problem lies in BPP when there is a polynomial time-constrained probabilistic algorithm that solves the problem and whose error probability is at most 1/3. The use of any other constant error limit smaller than 1/2 does not change the definition of the class BPP; by applying a given BPP algorithm several times, any desired error limit can be achieved.

BPP algorithms are Monte Carlo algorithms because they have a low probability of delivering a wrong result.

definition

A language is in the complexity class if and only if there is a probabilistic Turing machine for which the following applies: ${\ displaystyle {\ mathcal {L}}}$ ${\ displaystyle {\ mathcal {BPP}}}$ ${\ displaystyle M}$

${\ displaystyle M}$ runs for all inputs in polynomial time
${\ displaystyle x \ in {\ mathcal {L}} \ Rightarrow Pr [M (x) = 1] \ geq {\ frac {2} {3}}}$
${\ displaystyle x \ notin {\ mathcal {L}} \ Rightarrow Pr [M (x) = 0] \ geq {\ frac {2} {3}}}$

The constant 2/3 is chosen arbitrarily. Any constant really larger than 1/2 and even for a constant (where is the input length) leads to an equivalent definition. ${\ displaystyle {\ frac {1} {2}} + | x | ^ {- c}}$ ${\ displaystyle c> 0}$ ${\ displaystyle | x |}$

In contrast to the complexity class ZPP , it is required here that the runtime of the Turing machine is polynomial for all inputs. This requirement can be weakened so that, as with ZPP, the only requirement is that the expected value of the running time is limited by a polynomial; the two definitions are equivalent. ${\ displaystyle M}$

properties

BPP is completed under complement formation, union and editing. That means that for two languages too . So it is co-BPP = BPP. ${\ displaystyle L_ {1}, L_ {2} \ in {\ mathcal {BPP}}}$ ${\ displaystyle L_ {1} ^ {c}, L_ {1} \ cup L_ {2}, L_ {1} \ cap L_ {2} \ in {\ mathcal {BPP}}}$

There is no known BPP complete problem and there are indications that there are no BPP complete problems.

Relationship to other complexity classes

Inclusions between probabilistic complexity classes

The class BPP lies between the classes RP and co-RP, in which only one-sided errors are allowed, and PP , in which only an error limit smaller than 1/2 is required, which may also depend on the input length. So (RP co-RP) ⊆ BPP ⊆ PP applies . It is unknown whether the inclusions are real, since P ⊆ RP and PP ⊆ PSPACE . ${\ displaystyle \ cup}$

The relationship to the class NP is unknown, neither BPP ⊆ NP nor NP ⊆ BPP could be shown so far, but the latter is considered unlikely. BPP lies in the polynomial time hierarchy PH: If P = NP, PH collapses completely to PH = P, in this case BPP = P. ${\ displaystyle {\ mathcal {BPP}} \ subseteq \ Sigma _ {2} ^ {P} \ cap \ Pi _ {2} ^ {P}.}$

The class BQP is the corresponding concept to the class BPP for quantum computers . We have BPP ⊆ BQP.

Individual evidence

↑ Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, 1998, ISBN 0-201-53082-1 , pp. 259 .
^ Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 125 .
^ Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 132 .
^ Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 133 .
^ ^A ^b Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .
^ Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 198.202 .
^ Clemens Lautemann: BPP and the polynomial hierarchy . In: Information Processing Letters . tape 17 , no. 4 . Elsevier, 1983, p. 215-217 , doi : 10.1016 / 0020-0190 (83) 90044-3 .
↑ Johannes Köbler, Uwe Schöning, Jacobo Torán: The Graph Isomorphism Problem - It's Structural Complexity . Birkhäuser, 1993, ISBN 3-7643-3680-3 , p. 78 .

literature

J. Gill. Computational complexity of probabilistic Turing machines , SIAM Journal on Computing 6 (4): 675-695, 1977.
Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, Reading / Mass. 1995, ISBN 0-201-53082-1 .

Web links

BPP . In: Complexity Zoo. (English)

[Papa-1] Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, 1998, ISBN 0-201-53082-1 , pp. 259 .

[AB125-2] Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 125 .

[AB132-3] Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 132 .

[AB133-4] Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , pp. 133 .

[BoCr195-5] A ^b Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .

[BoCr198-6] Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 198.202 .

[Lau83-7] Clemens Lautemann: BPP and the polynomial hierarchy . In: Information Processing Letters . tape 17 , no. 4 . Elsevier, 1983, p. 215-217 , doi : 10.1016 / 0020-0190 (83) 90044-3 .

[KST78-8] Johannes Köbler, Uwe Schöning, Jacobo Torán: The Graph Isomorphism Problem - It's Structural Complexity . Birkhäuser, 1993, ISBN 3-7643-3680-3 , p. 78 .