BPP (complexity)

In complexity theory BPP ( bounded error probabilistic polynomial time engl. ) is a complexity class of decision problems. One problem is in BPP if there is a polynomial- time- bounded probabilistic algorithm that solves the problem and the error probability is at most 1/3. The use of any other constant error bound is less than 1/2 does not change the definition of the class BPP, by repeated application of a given BPP algorithm can achieve any error bound.

BPP algorithms are Monte Carlo algorithms as they provide with a low probability an incorrect result.

Definition

A language is present precisely in the complexity class if a probabilistic Turing machine exists, for which:

  • Runs for all the inputs in polynomial time

The constant 2/3 is chosen arbitrarily. Each constant is strictly greater than 1/2, and even for a constant ( which is the entry length ) resulting in an equivalent definition.

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

Properties

BPP is closed under complementation, union and intersection. This means that for two languages ​​as well. It is co -BPP = BPP.

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

Relation to other complexity classes

BPP is the class among the classes RP and co -RP, in which one-sided errors are only allowed and PP, in which only a small error bound 1/2 is required, which may also depend on the input length. It is therefore necessary (RP co -RP ) ⊆ BPP ⊆ PP. It is unknown whether the inclusions are genuine, since P ⊆ RP and PP ⊆ PSPACE is true, but it is unknown whether the inclusion P ⊆ PSPACE is real.

The relationship to the class NP is unknown, neither BPP ⊆ NP or NP ⊆ BPP has so far been shown, the latter is viewed as being unlikely. BPP is the Polynomialzeithierarchie PH: If P = NP, collapses completely PH PH = P, in this case would BPP = P.

The class BQP is the appropriate concept for the class BPP for quantum computers. It is BPP ⊆ BQP.

141971
de