The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that
Defined in [Bab85].
An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.
There exists an oracle relative to which BQP is not in MA [Wat00].
Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].
Shown in [San07] that MA/1 (that is, MA with 1 bit of advice) does not have circuits of size for any . In the same paper, the result was used to show that MA/1 cannot be solved on more than a fraction of inputs having length by any circuit of size . Finally, it was shown that MA does not have arithmetic circuits of size .
Same as BPP, except that now the computation paths need not all have the same length.
Defined in [HHT97], where the following was also shown:
There exists an oracle relative to which BPPpath is not contained in Σ2P [BGM02].
An alternate characterization of BPPpath uses the idea of post-selection. That is, BPPpath is the class of languages for which there exists a pair of polynomial-time Turing machines and such that the following conditions hold for all :
We say that is the post-selector. Intuitively, this characterization allows a BPP machine to require that its random bits have some special but easily verifiable property. This characterization makes the inclusion NP ⊆ BPPpath nearly trivial.
See Also: PostBQP (quantum analogue).
The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.
One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).
BQP is often identified as the class of feasible problems for quantum computers.
Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.
Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.
BQPBQP = BQP [BV97].
[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.
There exist oracles relative to which:
If P=BQP relative to a random oracle then BQP=BPP [FR98].
Is to BQP/mpoly as ∃BPP is to MA. Namely, the BQP machine is required to give some answer with probability at least 2/3 even if the advice is bad. Even though BQP/mpoly is a more natural class, BQP/poly follows the standard definition of advice as a class operator [KL82].
Contained in BQP/mpoly and contains BQP/log.
The class of problems for which there exists a BPP machine M such that, for all inputs x,
Alternatively defined as NPBPP.
Contains NP and BPP, and is contained in MA and SBP.
∃BPP seems obviously equal to MA, yet [FFK+93] constructed an oracle relative to which they're unequal! Here is the difference: if the answer is "yes," MA requires only that there exist a y such that for at least 2/3 of random strings r, M(x,y,r) accepts (where M is a P predicate). For all other y's, the proportion of r's such that M(x,y,r) accepts can be arbitrary (say, 1/2). For ∃BPP, by contrast, the probability that M(x,y) accepts must always be either at most 1/3 or at least 2/3, for all y's.
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 for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness.However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown thatIP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].
The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.
Here, Alice and Bob collectively constitute "Arthur", and the cost of an MAcc communication protocol is defined as the bit length of Merlin's message plus the communication cost of the ensuing randomized protocol between Alice and Bob. (Not charging for the length of Merlin's message would enable every function to be computed with constant cost in this model.)
Does not contain coNPcc (first shown by [Kla03]).
It is open to prove that there exists an explicit two-party function whose MAcc-type communication complexity is ω(n1/2).
The subclass of MA such that for each input size n, there is a sparse set Sn that Merlin's proof string always belongs to (no matter what the input is).
Defined in [KST93], where it is also observed that if graph isomorphism is in P/poly, then the complement of graph isomorphism is in MA'.
Same as MA, except now Arthur is E instead of polynomial-time.
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Same as MA, except now Arthur is EXP instead of polynomial-time, and the message from Merlin can be exponentially long.
There is a problem in MAEXP that does not have polynomial-size circuits [BFT98]. On the other hand, there is an oracle relative to which every problem in MAEXP does have polynomial-size circuits.
[MVW99] considered the best circuit lower bound obtainable for a problem in MAEXP, using current techniques. They found that this bound is half-exponential: i.e. a function f such that f(f(n))=2n. Such functions exist, but are not expressible using standard asymptotic notation.
Identical to MA except for that Arthur (the verifier) has random access to the proof string given by Merlin, and is limited to running times of order .
This class was used by [SM03] to show that if EXP has circuits of polynomial size, then EXP = MA.
Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Contained in NEEXP.
Nondeterministic exponential time (i.e. NTIME(2p(n)) for p a polynomial).
Equals MIP [BFL91] (but not relative to all oracles).
NEXP is in P/poly if and only if NEXP = MA [IKW01].
[KI02] show the following:
Does not equal EXP if and only if there is a sparse set in NP that is not in P.
There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].
The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].
The class of dashed hopes and idle dreams.
More formally: an "NP machine" is a nondeterministic polynomial-time Turing machine.
Then NP is the class of decision problems solvable by an NP machine such that
Equivalently, NP is the class of decision problems such that, if the answer is "yes," then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is "no," then the algorithm must declare invalid any purported proof that the answer is "yes."
For example, the SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.
A decision problem is NP-complete if (1) it is in NP, and (2) any problem in NP can be reduced to it (under some notion of reduction). The class of NP-complete problems is sometimes called NPC.
That NP-complete problems exist is immediate from the definition. The seminal result of Cook [Coo71], Karp [Kar72], and Levin [Lev73] is that many natural problems (that have nothing to do with Turing machines) are NP-complete.
The first such problem to be shown NP-complete was SAT [Coo71]. Other classic NP-complete problems include:
For many, many more NP-complete problems, see [GJ79].
There exists an oracle relative to which P and NP are unequal [BGS75]. Indeed, P and NP are unequal relative to a random oracle with probability 1 [BG81] (see [AFM01] for a novel take on this result). Though random oracle results are not always indicative about the unrelativized case [CCG+94].
There even exists an oracle relative to which the P versus NP problem is outside the usual axioms of set theory [HH76].
If we restrict to monotone classes, mP is strictly contained in mNP [Raz85].
Perhaps the most important insight anyone has had into P versus NP is to be found in [RR97]. There the authors show that no 'natural proof' can separate P from NP (or more precisely, place NP outside of P/poly), unless secure pseudorandom generators do not exist. A proof is 'natural' if it satisfies two conditions called constructivity and largeness; essentially all lower bound techniques known to date satisfy these conditions. To obtain unnatural proof techniques, some people suspect we need to relate P versus NP to heavy-duty 'traditional' mathematics, for instance algebraic geometry. See [MS02] (and the survey article [Reg02]) for a development of this point of view.
For more on P versus NP (circa 1992) see [Sip92]. For an opinion poll, see [Gas02]. P vs NP is a "Millenium Prize" problem [CMI00].
If P equals NP, then NP equals its complement coNP. Whether NP equals coNP is also open. NP and coNP can be extended to the polynomial hierarchy PH.
The set of decision problems in NP, but not in P or NPC, is sometimes called NPI. If P does not equal NP then NPI is nonempty [Lad75].
Probabilistic generalizations of NP include MA and AM. If NP is in coAM (or BPP) then PH collapses to Σ2P [BHZ87].
PH also collapses to Σ2P if NP is in P/poly [KL82].
There exist oracles relative to which NP is not in BQP [BBB+97].
An alternate characterization is NP = PCP(log n, O(1)) [ALM+98].
Also, [Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic. This leads to the subclass SNP.
It is known that if any NP-complete language is sparse (contains no more than a polynomial number of strings of length ), then P = NP. [BH08] improved this result, showing that if any language in NP has an NP-hard set of subexponential density, then coNP is contained in NP/poly and thus, by [Yap82], PH collapses to the third level.
NP is equal to SO-E, the second-order queries where the second-order quantifiers are only existantials.
The class of functions computable in randomized polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of MA.
L is in OMA if there exists a randomized, polynomial time verifier V taking an input and a witness, so that:
NP is contained in OMA iff NP is in P/poly [FSW09].
EXP is contained in P/poly iff EXP = OMA [FSW09].
BPP is contained in OMA [GM15].
Implicit in [San07] that OMA/1 (that is, OMA with 1 bit of trusted advice) does not have circuits of size for any .
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 for which a "yes" answer can be verified by a quantum computer with access to a classical proof. Also known as the subclass of of QMA with classical witnesses. Defined in [AN02].
Called MQA by Watrous [Wat09].
Contains MA, and is contained in QMA.
Given a black-box group G and a subgroup H, the problem of testing non-membership in H has polynomial QCMA query complexity [AK06].
See [AK06] for a "quantum oracle separation" between QCMA and QMA. No classical oracle separation between QCMA and QMA is currently known.
The problem GROUND STATE CONNECTIVITY, which intuitively asks whether a local Hamiltonian's ground space has an "energy barrier", is QCMA-complete [GS15]. Roughly: Given a local Hamiltonian H and ground states v and w, is there a polynomial-length sequence of local unitary operations mapping v to w, such that each intermediate state encountered remains in the ground space of H?
The class of decision problems such that a "yes" answer can be verified by a 1-message quantum interactive proof. That is, a BQP (i.e. quantum polynomial-time) verifier is given a quantum state (the "proof"). We require that
QMA = QIP(1).
Defined in [Wat00], where it is also shown that group non-membership is in QMA.
Based on this, [Wat00] gives an oracle relative to which MA is strictly contained in QMA.
Kitaev and Watrous (unpublished) showed QMA is contained in PP (see [MW05] for a proof). Combining that result with [Ver92], one can obtain an oracle relative to which AM is not in QMA.
Kitaev ([KSV02], see also [AN02]) showed that the 5-Local Hamiltonians Problem is QMA-complete. Subsequently, Kempe and Regev [KR03] showed that even 3-Local Hamiltonians is QMA-complete. A subsequent paper by Kempe, Kitaev, and Regev [KKR04], has hit rock bottom (assuming P does not equal QMA), by showing 2-local Hamiltonians QMA-complete.
Compare to NQP.
If QMA = PP then PP contains PH [Vya03]. This result uses the fact that QMA is contained in A0PP.
Approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete [AGK07].
See also: QCMA, QMA/qpoly, QSZK, QMA(2), QMA-plus.
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 the following holds. There exists a #P function f and an FP function g such that, for all inputs x,
Defined in [BGM02], where the following was also shown:
There exists an oracle relative to which SBP is not closed under intersection [GLM+15].
If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = AM [Vol20].
The probabilistic analogue of YP; it is to YP what MA is to NP. Formally, the class of decision problems for which there exists a syntactic BPP machine M such that:
To amplify a YPP machine, one can run it multiple times, then accept if a majority of runs accept, reject if a majority reject, and otherwise output "I don't know."
Contains BPP and YP, and is contained in MA and P/poly.
Is to YPP as BQP is to BPP, and QMA is to MA. The machine is now a quantum computer and the advice is a quantum state |ψ_n>.
Contains BQP and YPP, and is contained in QMA and BQP/qpoly.
![{\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]\geq {\frac {2}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68f589f128ac94d15db09cab8923d093aeebf7a6)
![{\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]<{\frac {1}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa07825632386c5a2f15399d38ace554cadfc5fc)
![{\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (n)}}\left[B(x,r)\right]>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc73cfc4e16ce114e19abb95ae8f9a730408f04a)
