Class Description

BPTIME(f(n)): Bounded-Error Probabilistic f(n)-Time

Same as BPP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [Gil77].

BPTIME(n^{log n}) does not equal BPTIME(2^{n^ε}) for any ε>0 [KV88]. Proving a stronger time hierarchy theorem for BPTIME is a longstanding open problem; see [BH97] for details.

[Bar02] has shown the following:

• If we allow a small number of advice bits (say log n), then there is a strict hierarchy: for every d at least 1, BPTIME(n^d)/(log n) does not equal BPTIME(n^d+1)/(log n).
• In the uniform setting, if BPP has complete problems then BPTIME(n^d) does not equal BPTIME(n^d+1).
• BPTIME(n) does not equal NP.

Subsequently, [FS04] managed to reduce the number of advice bits to only 1: BPTIME(n^d)/1 does not equal BPTIME(n^d+1)/1. They also proved a hierarchy theorem for HeurBPTIME.

For another bounded-error hierarchy result, see BPQP.

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 Σ₂P ∩ Π₂P [Lau83], and indeed in ZPP^NP [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 O₂P since problems requiring exponential sized circuits can be verified in O₂E [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(n^c) 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: BPP_path.

More about...

BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2^{O((log n)^k)}); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.

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

If either (1) #P does not have a subexponential-time bounded-error algorithm, or (2) EXP does not have subexponential-size circuits, then the BPQP hierarchy is strict -- that is, for all a < b at least 1, BPTIME(2^{(log n)^a}) is strictly contained in BPTIME(2^{(log n)^b}).

More about...

HeurBPTIME(f(n)): Heuristic BPTIME(f(n))

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPTIME(f(n)) machine. Thus, HeurBPTIME(f(n)) has the same relationship with BPTIME as HeurDTIME.

Thus HeurBPP is the union of HeurBPTIME(n^c) over all c.

More about...