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:
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.