Class Description

BPPpath: Threshold BPP

Same as BPP, except that now the computation paths need not all have the same length.

Defined in [HHT97], where the following was also shown:

There exists an oracle relative to which BPPpath is not contained in Σ2P [BGM02].

An alternate characterization of BPPpath uses the idea of post-selection. That is, BPPpath is the class of languages for which there exists a pair of polynomial-time Turing machines and such that the following conditions hold for all :

We say that is the post-selector. Intuitively, this characterization allows a BPP machine to require that its random bits have some special but easily verifiable property. This characterization makes the inclusion NP ⊆ BPPpath nearly trivial.

See Also: PostBQP (quantum analogue).

Linked From

BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes' then at least 2/3 of the computation paths accept.
  2. If the answer is 'no' then at most 1/3 of the computation paths accept.

(Here all computation paths have the same length.)

Often identified as the class of feasible problems for a computer with access to a genuine random-number source.

Defined in [Gil77].

Contained in Σ2PΠ2P [Lau83], and indeed in ZPPNP [GZ97].

If BPP contains NP, then RP = NP [Ko82,Gil77] and PH is contained in BPP [Zac88].

If any problem in E requires circuits of size 2Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).

Contained in O2P since problems requiring exponential sized circuits can be verified in O2E [GLV24] [Li23] which can be used to derandomize [IW97].

Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].

BPP is not known to contain complete languages. [Sip82], [HH86] give oracles relative to which BPP has no complete languages.

There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].

In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(nc) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.

A zero-one law exists stating that BPP has p-measure zero unless BPP = EXP [Mel00].

Equals Almost-P.

See also: BPPpath.

More about...


BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQPBQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

If P=BQP relative to a random oracle then BQP=BPP [FR98].

More about...


PostBPP: BPP With Postselection

Alias for BPPpath.

More about...


PostBQP: BQP With Postselection

A class inspired by the proverb, "if at first you don't succeed, try, try again."

Formally, the class of decision problems solvable by a BQP machine such that

Defined in [Aar05b], where it is also shown that PostBQP equals PP.

[Aar05b] also gives the following alternate characterizations of PostBQP (and therefore of PP):

More about...


SBP: Small Bounded-Error Probability

The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,

  1. If the answer is "yes" then f(x) > g(x).
  2. If the answer is "no" then f(x) < g(x)/2.

Defined in [BGM02], where the following was also shown:

There exists an oracle relative to which SBP is not closed under intersection [GLM+15].

If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = AM [Vol20].

More about...