Class Description

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}).

Linked From

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.

More about...