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(nlog n) does not equal BPTIME(2n^ε) 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:

Subsequently, [FS04] managed to reduce the number of advice bits to only 1: BPTIME(nd)/1 does not equal BPTIME(nd+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 Σ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...


BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2O((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:

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(nc) over all c.

More about...