Defined as the class of problems solvable by randomized algorithms that always return the correct answer, and whose expected running time (on any input) is polynomial, in [Gil77]. (Proposition 5.5(iii) in this paper shows that the two definitions above are equivalent.)
Contains the problem of testing whether an integer is prime [SS77] [AH87].
In contrast to BPP and RP, it is not known whether showing ZPP = P requires proving superpolynomial circuit lower bounds [KI02].
There exists an oracle relative to which ZPP = EXP [Hel84a], [Hel84b], [Kur85], [Hel86].
Has the same p-measure as RP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].
The exponential-time analogue of ⊕P.
There exists an oracle relative to which ⊕EXP = ZPP [BBF98].
The class of decision problems solvable by an NP machine such that
(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.
The class CSPACE with work space and catalytic space .
Contains TC1 and is contained in ZPP [BCKLS14].
Defined in [BCKLS14].
Equals DTIME(2O(n)).
Does not equal NP [Boo72] or PSPACE [Boo74] relative to any oracle. However, there is an oracle relative to which E is contained in NP (see ZPP), and an oracle relative to PSPACE is contained in E (by equating the former with P).
There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [Wat87].
Problems hard for BPP under Turing reductions have measure 1 in E [AS94].
It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then BPP does not equal EXP.
[IT89] gave an oracle relative to which E = NE but still there is an exponential-time binary predicate whose corresponding search problem is not in E.
[BF03] gave a proof that if E = NE, then no sparse set is collapsing, where they defined a set to be collapsing if and if for all such that and are Turing reducible to each other, and are many-to-one reducible to each other.
Contrast with EXP.
Equals the union of DTIME(2p(n)) over all polynomials p.
If EXP is in P/poly then EXP = MA [BFL91].
Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].
There exist oracles relative to which
[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.
[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MAPOLYLOG such that no deterministic polynomial-time adversary can generate a list of inputs for a P problem that includes one which fails to be simulated. As a result, EXP ⊆ MA if EXP has circuits of polynomial size.
[SU05] show that EXP NP/poly implies EXP P||NP/poly.
In descriptive complexity EXPTIME can be defined as SO() which is also SO(LFP)
The class of decision problems solvable by a family of polynomial-size Boolean circuits. The family can be nonuniform; that is, there could be a completely different circuit for each input length.
Equivalently, P/poly is the class of decision problems solvable by a polynomial-time Turing machine that receives a trusted 'advice string,' that depends only on the size n of the input, and that itself has size upper-bounded by a polynomial in n.
Contains BPP by the progenitor of derandomization arguments [Adl78] [KL82]. By extension, BPP/poly, BPP/mpoly, and BPP/rpoly all equal P/poly. (By contrast, there is an oracle relative to which BPP/log does not equal BPP/mlog, while BPP/mlog and BPP/rlog are not equal relative to any oracle.)
[KL82] showed that, if P/poly contains NP, then PH collapses to the second level, Σ2P.
They also showed:
It was later shown that, if NP is contained in P/poly, then PH collapses to ZPPNP [KW98] and indeed to O2P [CR06] (which is unconditionally included in P/poly). This seems close to optimal, since there exists an oracle relative to which the collapse cannot be improved to Δ2P [Wil85].
If NP is not contained in P/poly, then P does not equal NP. Much of the effort toward separating P from NP is based on this observation. However, a 'natural proof' as defined by [RR97] cannot be used to show NP is outside P/poly, if there is any pseudorandom generator in P/poly that has hardness 2Ω(n^ε) for some ε>0.
If NP is contained in P/poly, then MA = AM [AKS+95]
The monotone version of P/poly is mP/poly.
P/poly has measure 0 in E with Σ2P oracle [May94b].
Strictly contains IC[log,poly] and P/log.
The complexity class of P with untrusted advice depending only on input size is ONP.
The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)
Has the same relation to NC as BQP does to P.
[CW00] showed that factoring is in ZPP with a QNC oracle.
Is incomparable with BPP as far as anyone knows.
See also: RNC.
The class of decision problems solvable by an NP machine such that
Defined in [Gil77] (implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2).
Contains the problem of testing whether an integer is prime [AH87], although this problem was subsequently shown to be in P [AKS02].
For other problems in RP, see the standard text on randomized algorithms, [MR95].
Has the same p-measure as ZPP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].
The class of decision problems for which there is a polynomial-time predicate P such that, on input x,
Note that this differs from Σ2P in that the quantifiers in the second condition are reversed.
Less formally, S2P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee. In Σ2P, the prover moves first.
Defined in [RS98], where it was also shown that S2P contains MA and Δ2P. Defined independently in [Can96].
Contains (and contrast with) O2P. If NP is contained in P/poly then PH = S2P (attributed to Sengupta in [Cai01]), and even is equal to O2P [CR06].
The class of decision problems for which there exists a polynomial-time machine M such that:
Defined in a recent post of the blog Shtetl-Optimized. See there for an explanation of the class's name.
Contains ZPP by the same argument that places BPP in P/poly.
Also contains P with TALLY ∩ NP ∩ coNP oracle.
Is contained in NP ∩ coNP and YPP.
Is equal to ONP ∩ coONP.
Defined as RBQP ∩ coRBQP. Equivalently, the class of problems in NP ∩ coNP such that both positive and negative witnesses are in FBQP.
For example, the language of square-free numbers is in ZBQP, because factoring is in FBQP and a factorization can be certified in ZPP (indeed in P, by [AKS02]).
Unlike EQP or ZQP, ZBQP would generalize ZPP in practice if quantum computers existed, in the sense that it provides proven answers.
Contains ZPP and is contained in RBQP and ZQP. Also, ZBQPZBQP = ZBQP. Defined here to clarify EQP and ZQP.
Same as ZPP, but with 2O(n)-time instead of polynomial-time.
ZPE = EE if and only if ZPP = EXP [IKW01].
Has the same relationship to BP•L as ZPP has to BPP. More specifically, the set of languages with a log space, polynomial time Turing machine using a read only randomness tape such that on input x:
1. With high probability over the random bits used in the randomness tape will the machine correctly output whether x is in the language.
2. The machine will either wither correctly output whether x is in the language, or output 'unknown'.
Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.
Contained in BP•L.
Equals Pcc if defined in terms of total functions; is not contained in ⊕Pcc if defined in terms of partial functions [GPW16b].
Same as ZPP, but with O(f(n))-time instead of polynomial-time.
For any constructible superpolynomial f, ZPTIME(f(n)) with NP oracle is not contained in P/poly [KW98].
