Difference between revisions of "Complexity Zoo:P"
Emil Jeřábek (talk | contribs) |
(→PP: Probabilistic Polynomial-Time: update ref for result PP does not have small quantum circuits) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 575: | Line 575: | ||
[[#ph|PH]] is in [[#ppp2|P<sup>PP</sup>]] [[zooref#tod89|[Tod89]]]. | [[#ph|PH]] is in [[#ppp2|P<sup>PP</sup>]] [[zooref#tod89|[Tod89]]]. | ||
− | [[Complexity Zoo:B#bpp|BPP]] [[zooref#kst89b|[KST+89b]]] and even [[Complexity Zoo:B#bqp|BQP]] [[zooref#fr98|[FR98]]] are low for PP: i.e., PP<sup>BQP</sup> = PP. Equals [[#postbqp|PostBQP]] [[zooref#aar05b|[Aar05b]]]. | + | [[Complexity Zoo:B#bpp|BPP]] [[zooref#kst89b|[KST+89b]]] and even [[Complexity Zoo:B#bqp|BQP]] [[zooref#fr98|[FR98]]] and [[Complexity Zoo:Y#yqp*|YQP*]] [[zooref#yir24|[Yir24]]] are low for PP: i.e., PP<sup>BQP</sup> = PP. <br> |
+ | [[Complexity Zoo:A#app|APP]] is PP-low [[zooref#li93|[Li93]]]. | ||
+ | |||
+ | Equals [[#postbqp|PostBQP]] [[zooref#aar05b|[Aar05b]]]. | ||
For a random oracle A, PP<sup>A</sup> is strictly contained in [[#pspace|PSPACE]]<sup>A</sup> with probability 1 [[zooref#abf94|[ABF+94]]]. | For a random oracle A, PP<sup>A</sup> is strictly contained in [[#pspace|PSPACE]]<sup>A</sup> with probability 1 [[zooref#abf94|[ABF+94]]]. | ||
− | For any fixed k, there exists a language in PP that does not have circuits of size n<sup>k</sup> [[zooref#vin04b|[Vin04b]]]. | + | For any fixed k, there exists a language in PP that does not have circuits of size n<sup>k</sup> [[zooref#vin04b|[Vin04b]]]. <br> |
+ | Indeed, there exists a language in PP that does not even have quantum circuits of size n<sup>k</sup> with quantum advice [[zooref#aar06|[Aar06]]] and [[zooref#yir24|[Yir24]]]. | ||
By contrast, there exists an oracle relative to which PP has linear-size circuits [[zooref#aar06|[Aar06]]]. | By contrast, there exists an oracle relative to which PP has linear-size circuits [[zooref#aar06|[Aar06]]]. |
Latest revision as of 15:53, 7 July 2024
Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References
Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z
Lists of related classes: Communication Complexity - Hierarchies - Nonuniform
P - P/log - P/poly - P#P - P#P[1] - PCTC - PAC0 - PBP - k-PBP - PC - Pcc - Pcc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PDQP - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PHcc - Φ2P - PhP - Π2P - PINC - PIO - PK - PKC - PL - PL1 - PL∞ - PLF - PLL - P-LOCAL - P-RLOCAL - PLS - PNP - PNPcc - P||NP - PNP[k] - PNP[log] - PNP[log^2] - P-OBDD - PODN - polyL - PostBPP - PostBPPcc - PostBQP - PP - PPcc - PP/poly - PPA - PPAD - PPADS - PPP - PPP - PPSPACE - PQMA[log] - PQUERY - PR - PR - PrHSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACEcc - PSPACE/poly - PT1 - PTAPE - PTAS - PT/WK(f(n),g(n)) - PZK
P: Polynomial-Time
The class that started it all.
The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)
Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.
Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].
Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.
Important subclasses of P include L, NL, NC, and SC.
P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.
Efforts to generalize P resulted in BPP and BQP.
The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.
In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)
P queries are exactly the one that can be written in the While/cons languages.
P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.
P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].
P/log: P With Logarithmic Advice
Same as P/poly, except that the advice string for input size n can have length at most logarithmic in n, rather than polynomial.
Strictly contained in IC[log,poly].
If NP is contained in P/log then P = NP.
P/poly: Nonuniform Polynomial-Time
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.
P#P: P With #P Oracle
I decided this class is so important that it deserves an entry of its own, apart from #P.
Contains PH [Tod89], and is contained in CH and in PSPACE.
Equals PPP (exercise for the visitor).
P#P[1]: P With Single Query To #P Oracle
Contains PH [Tod89]. Indeed, contains MP, which in turn contains ModPH [GKR+95].
PCTC: P With Closed Time Curves
Same as P with access to bits along a closed time curve.
Implicitly defined in [Aar05c], where it was shown that PSPACE = PCTC.
See also BQPCTC.
para-: Parameterized Complexity
The para- prefix indicates that a complexity class is parameterized by some other measure of complexity. Specifically, a language L is in the parameterized class para-C, if there is an alphabet A and a computable function pi(k) -> A*, such that every (Q,k) is in para-L if and only if (Q,pi(k)) in L.
The prototypical example (as well the violation of the naming convention) is para-P, which is almost always known as FPT, which is equal to DTIME(f(k)n^c) for some constant c.
Space-parameterized examples include para-L and para-NL, which are equal to DSPACE(f(k)+log(n)) and NDSPACE(f(k)+log(n)), respectively.
Compare with the slicewise complexity classes X-, such as X-.
Discussed in: J. Flum and M. Grohe. Describing parameterized complexity classes. Information and Computation. and Elberfeld M., Stockhusen C., Tantau T. (2012) On the Space Complexity of Parameterized Problems.
para-L: Parameterized Logspace
para- version of L. Equivalent to DSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized logspace, XL.
Parameterized vertex cover (is there a vertex cover of size at most k) is complete for para-L. (Elberfeld et al, 2012)
para-NL: Parameterized Nondeterministic Logspace
para- version of NL. Equivalent to NDSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized nondeterministic logspace, XNL.
It seems open whether there are natural complete problems for para-NL. However, the related class para-NL[f log] has many natural complete problems.
para-NL[f log]: Parameterized Nondeterministic Logspace
Like para-NL, but where the number of nondeterministic branches is bounded by O(f(k) log(n)).
A natural complete is problem parameterized distance: is there a path on directed graph G from vertex s to v, of length at most k? (Elberfeld et al, 2012)
para-NL[f log] is contained within XL, slicewise logspace.
para-P: Parameterized Polynomial time.
para-P is a less common name for FPT, but in line with other para- classes naming conventions. Its slicewise counterpart is still called XP.
PAC0: Probabilistic AC0
The Political Action Committee for computational complexity research.
The class of problems for which there exists a DiffAC0 function f such that the answer is "yes" on input x if and only if f(x)>0.
Equals TC0 and C=AC0 under logspace uniformity [ABL98].
PBP: Polynomial-Size Branching Program
Same as k-PBP but with no width restriction.
k-PBP: Polynomial-Size Width-k Branching Program
A branching program is a directed acyclic graph with a designated start vertex. Each (non-sink) vertex is labeled by the name of an input bit, and has two outgoing edges, one of which is followed if that input bit is 0, the other if the bit is 1. A sink vertex can be either an 'accept' or a 'reject' vertex.
The size of the branching program is the number of vertices. The branching program has width k if the vertices can be sorted into levels, each with at most k vertices, such that each edge goes from a level to the one immediately after it.
Then k-PBP is the class of decision problems solvable by a family of polynomial-size, width-k branching programs. (A uniformity condition may also be imposed.)
k-PBP equals (nonuniform) NC1 for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC0 [BT88].
Contained in k-EQBP, as well as PBP.
See also BPd(P).
PC: Polynomial-Time Over The Complex Numbers
An analog of P for Turing machines over a complex number field.
Defined in [BCS+97].
Pcc: Communication Complexity P
In a two-party communication complexity problem, Alice and Bob have n-bit strings x and y respectively, and they wish to evaluate some Boolean function f(x,y) using as few bits of communication as possible. Pcc is the class of (infinite families of) f's, such that the amount of communication needed is only O(polylog(n)), even if Alice and Bob are restricted to a deterministic protocol.
Note that all functions of the form above are solvable given bits of communication, since no bounds are placed on the computational abilities of Alice and Bob. Thus, when discussing this class, "polynomially" is sometimes used in place of "polylogarithmically."
Is strictly contained in NPcc and in BPPcc because of the EQUALITY problem.
If the classes are defined in terms of total functions, then Pcc = NPcc ∩ coNPcc = UPcc.
Defined in [BFS86].
Pcc: Pcc in NOF model, players
Like Pcc, but with players, where each player can see all of the other player's bits, but not their own. Intuitively, each player has their bits written on their forehead.
More formally, Pcc is the class of functions where for all , , such that is solvable in a deterministic sense by players, each of which is aware of all inputs other than his own, and such that bits of communication are used.
Pcc is trivially contained in BPPcc, RPcc and NPcc.
PCD(r(n),q(n)): Probabilistically Checkable Debate
The class of decision problems decidable by a probabilistically checkable debate system, as follows.
Two debaters B and C alternate writing strings on a "debate tape," with B arguing that the answer is "yes" and C arguing the answer is "no." Then a polynomial-time verifier flips O(r(n)) random coins and makes O(q(n)) nonadaptive queries to the debate tape (meaning that they depend only on the input and the random coins, not the results of previous queries). The verifier then outputs an answer, which should be correct with high probability.
Defined in [CFL+93], who also showed that PCD(log n, 1) = PSPACE. This result was used to show that certain problems are PSPACE-hard even to approximate.
Contained in GPCD(r(n),q(n)).
P-Close: Problems Close to P
The class of decision problems solvable by a polynomial-time algorithm that outputs the wrong answer on only a sparse (that is, polynomially-bounded) set of instances.
Defined in [Yes83].
Contains Almost-P and is contained in P/poly [Sch86].
PCP(r(n),q(n)): Probabilistically Checkable Proof
The class of decision problems such that a "yes" answer can be verified by a probabilistically checkable proof, as follows.
The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a proof (which might be exponentially long), but can query only O(q(n)) bits of the proof.
Then we require the following:
- If the answer is "yes," there exists a proof such that the verifier accepts with certainty.
- If the answer is "no," then for all proofs the verifier rejects with probability at least 1/2 (over the choice of the O(r(n)) random bits).
Defined in [AS98].
By definition NP = PCP(0,poly(n)).
MIP = PCP(poly(n),poly(n)).
PCP(r(n),q(n)) is contained in NTIME(2O(r(n))q(n) + poly(n)).
NP = PCP(log n, log n) [AS98].
In fact, NP = PCP(log n, 1) [ALM+98]!
On the other hand, if NP is contained in PCP(o(log n), o(log n)), then P = NP [FGL+91].
Also, even though there exists an oracle relative to which NP = EXP [Hel84], if we could show there exists an oracle relative to which PCP(log n, 1) = EXP, then we'd have proved P not equal to NP [For94].
Another weird oracle fact: since NP does not equal NEXP [SFM78], PCP(log n, log n) does not equal PCP(poly(n), poly(n)). However, there exist oracles relative to which the latter inequality is false [HCC+92].
PDQP: Product Dynamical Quantum Polynomial time
This class is a generalization of BQP where one is allowed to perform measuresments without collapsing the wavefunction.[ABFL14]
Unlike, BQP this is likely to be a not physically realizable class.
Contains SZK and thus contains graph isomorphism.
There is an oracle relative to which BQP is not equal to PDQP and an oracle relative to which NP is not contained in PDQP.
PDQP can perform unordered searches faster than BQP.
Compare DQP.
PermUP: Self-Permuting UP
The class of languages L in UP such that the mapping from an input x to the unique witness for x is a permutation of L.
Contains P.
Defined in [HT03], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is UP.
On the other hand, they show that if PermUP = UP then E = UE.
See also: SelfNP.
PEXP: Probabilistic Exponential-Time
Has the same relation to EXP as PP does to P.
Is not contained in P/poly [BFT98].
PF: Alternate Name for FP
PFCHK(t(n)): Proof-Checker
The class of decision problems solvable in time O(t(n)) by a nondeterministic Turing machine, as follows. The machine is given oracle access to a proof string of unbounded length.
- If the answer is "yes," then there exists a value of the proof string such that all computation paths accept.
- If the answer is "no," then for all values of the proof string, there exists a computation path that rejects.
Credited in [For94] to S. Arora, R. Impagliazzo, and U. Vazirani.
An interesting question is whether NP = PFCHK(log n) relative to all possible oracles. Fortnow [For94] observes that the answer depends on what oracle access mechanism is used.
PH: Polynomial-Time Hierarchy
Let Δ0P = Σ0P = Π0P = P. Then for i>0, let
Then PH is the union of these classes for all nonnegative constants i.
PH can also be defined using alternating quantifiers: it's the class of problems of the form, "given an input x, does there exist a y such that for all z, there exists a w ... such that φ(x,y,z,w,...)," where y,z,w,... are polynomial-size strings and φ is a polynomial-time computable predicate. It's not totally obvious that this is equivalent to the first definition, since the first one involves adaptive NP oracle queries and the second one doesn't, but it is.
Defined in [Sto76].
Contained in P with a PP oracle [Tod89].
Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].
Furthermore, there exist oracles separating any ΣiP from Σi+1P. In fact, relative to a random oracle, the hierarchy is infinite: each level is strictly contained in the next, with probability 1 [RST15] (this was an open problem for 29 years). Previously, it had been known that if it had collapsed relative to a random oracle, then it would have collapsed unrelativized [Boo94].
It was shown in [CPO7] that if the NP Machine Hypothesis holds, then .
For a compendium of problems complete for different classes of the Polynomial Hierarchy see [Sch02a] and [Sch02b].
PH is equal to the set of boolean queries recognizable by a concurent random acess machine using exponentially many processors and constant time[Imm89].
Since NP is the class of query expressible in second-order existantial logic, PH can also be defined as the query expressible in second-order logic.
PHcc: Communication Complexity PH
The polynomial hierarchy for communication complexity, naturally built with NPcc and coNPcc forming the first level. Specifically, a cost-k protocol in the PHcc model corresponds to a constant-depth 2k-ary tree whose internal nodes are alternating layers of AND and OR gates, and whose leaves represent (the indicator functions of) either rectangles or complements of rectangles, as appropriate.
It is unknown whether Σ2cc equals Π2cc.
Defined in [BFS86], where it was also shown (among other things) that BPPcc is contained in Σ2cc ∩ Π2cc.
Φ2P: Second Level of the Symmetric Hierarchy, Alternative Definition
The class of problems for which there exists a polynomial-time predicate P(x,y,z) such that for all x, if the answer on input x is "yes," then
- For all y, there exists a z for which P(x,y,z).
- For all z, there exists a y for which P(x,y,z).
Defined in [Can96], where it was also observed that Φ2P = S2P.
PhP: Physical Polynomial-Time
Defined by Valiant [Val03] to be "the class of physically constructible polynomial resource computers" (characterizing what "can be computed in the physical world in practice"). There he says that PhP contains P and BPP, but that it is open whether PhP contains BQP, since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.
For what it's worth, the present zookeeper has more qualms about admitting DTIME(n1000) into PhP than BQTIME(n2). It is very possible that the total number of bits or bit tranisitions that can be witnessed by any one observer in the universe is finite. (Recent observations of the cosmological constant combined with plausible fundamental physics yields a bound of 10k with k in the low hundreds.) In practice, less than 1050 bits and less than 1080 bit transitions are available for human use. (This is combining the number of atoms in the Earth with the number of signals that they can exchange in a millenium.)
The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether BQP is a realistic class.
Π2P: coNP With NP Oracle
Complement of Σ2P.
Along with Σ2P, comprises the second level of PH, the polynomial hierarchy. For any fixed k, there is a problem in Π2P ∩ Σ2P that cannot be solved by circuits of size nk [Kan82].
PINC: Polynomial Ignorance of Names of Classes
(Actually, I've since been informed that PINC means "Incremental Polynomial-Time.")
The class of function problems, f:{0,1}n->{0,1}m, such that the kth output bit is computable in time polynomial in n and k.
Defined in [JY88].
Contained in PIO. This containment is strict, since if m=2n (say), then computing the first bit of f(x) might be EXP-complete.
PIO: Polynomial Input Output
The class of function problems, f:{0,1}n->{0,1}m, such that f(x) is computable in time polynomial in n and m. Allows us to discuss whether a function is "efficiently computable" or not, even if the output is too long to write down in polynomial time.
Defined in [Yan81].
Strictly contains PINC.
PK: P With Kolmogorov-Complexity Oracle
P equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.
A similar class was defined in [ABK+02], where it was also shown that PK contains PSPACE. It is not known whether PK contains all of R, or even any recursive problem not in PSPACE.
See also: BPPKT.
PKC: Perfect Knowledge Complexity
Has the same relation to PZK as SKC does to SZK.
Defined in [GP91].
PL: Probabilistic L
Has the same relation to L that PP has to P.
Contains BPL and contained in DET [Coo85].
PLPL = PL (see [HO02]).
PL1: Polynomially-Bounded L1 Spectral Norm
The class of Boolean functions f:{-1,1}n->{-1,1} such that the sum of absolute values of Fourier coefficients of f is bounded by a polynomial in n.
Defined in [BS90], where it was also shown that PL1 is contained in PT1 (and this inclusion is strict).
PL∞: Polynomially-Bounded L∞-1 Spectral Norm
The class of Boolean functions f:{-1,1}n->{-1,1} such that the maximum of |α|-1, over all Fourier coefficients α of f, is upper-bounded by a polynomial in n.
Defined in [BS90], where it was also shown that PL∞ contains PT1 (and this inclusion is strict).
PLF: Polynomial Leaf
Defined in [Pap90].
I believe it's the same as PPA.
PLL: Polynomial Local Lemma
The class of TFNP function problems that are guaranteed to have a solution because of the Lovász Local Lemma. Defined in [Pap94b].
P-LOCAL: Polylogarithmic rounds in the LOCAL model
The family of locally checkable problems that can be solved by deterministic algorithms in poly(log n) rounds of the LOCAL model of computation on an n node graph.
In the local model of computation, there is a graph with n vertices, each with its own, unique Θ(log(n)) bit ID. Each vertex starts with the state of knowing only its ID and has unbounded, deterministic, computational ability. At each round, every vertex synchronously sends and receives one unbounded message from each neighbor. At the end of the algorithm, each vertex gives an output satisfying the problem. For instance, the vertices may output a valid coloring.
Proven in [RG20] that P-LOCAL = P-RLOCAL.
P-RLOCAL: Polylogarithmic rounds in the Randomized LOCAL model
The family of locally checkable problems that can be solved by randomized algorithms in poly(log n) rounds of the LOCAL model of computation on an n node graph.
The same as P-LOCAL, except now the vertices may use randomness in the messages they send and their final output, and must give a valid output with probability at least 1 - 1/n.
Proven in [RG20] that P-LOCAL = P-RLOCAL.
PLS: Polynomial Local Search
The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite directed acyclic graph has a sink."
More precisely, for each input, there's a finite set of solutions (i.e. strings), and a polynomial-time algorithm that computes a cost for each solution, and a neighboring solution of lower cost provided that one exists. Then the problem is to return any solution that has cost less than or equal to all of its neighbors. (In other words, a local optimum.)
(Note: In the Zookeeper's humble opinion, PLS should have been defined as follows: there exist polynomial-time algorithms that compute the cost of a solution, and the set of all neighbors of a given solution, not just a single solution of lower cost. Of course we'd require that every solution has only polynomially many neighbors. The two definitions are not obviously equivalent, and it's conceivable that knowing all the neighbors would be helpful -- for example, in simulated annealing one sometimes makes uphill moves.)
(Note to Note: The equivalance of these classes was shown (though not stated explicitly) in Theorem 1 of [JPY88].)
There exists an oracle relative to which PLS is not contained in FBQP [Aar03].
Also, there exist oracles relative to which PLS is not contained in PPA [BM04] or PPP [GHJ+22], and PPA and PPP are not contained in PLS [Mor01].
[CT07] conjecture that if PPAD is in P, then PLS is in P.
PNP: P With Oracle Access To NP
See Δ2P.
PNPcc: Communication Complexity PNP
Not contained in PPcc [BVW07].
Does not contain BPPcc if partial functions are allowed [PPS14].
Contained in UPostBPPcc.
P||NP: P With Parallel Queries To NP
Equals PNP[log] ([BH91] and [Hem89] independently).
PNP[k]: P With k NP Queries(for constant k)
Equals P with 2k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
If PNP[1] = PNP[2], then PNP[1] = PNP[log] and indeed PH collapses to Δ3P (attributed in [Har87b] to J. Kadin).
PNP[log]: P With Log NP Queries
Also known as Θ2P.
The class of decision problems solvable by a P machine, that can make O(log n) queries to an NP oracle (where n is the length of the input).
Equals P||NP, the class of decision problems solvable by a P machine that can make polynomially many nonadaptive queries to an NP oracle (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
PNP[log] is contained in PP [BHW89].
Determining the winner in an election system proposed in 1876 by Charles Dodgson (a.k.a. Lewis Carroll) has been shown to be complete for PNP[log] [HHR97].
Contains PNP[k] for all constants k.
PNP[log^2]: P With Log2 NP Queries
Same as PNP[log], except that now log2 queries can be made.
The model-checking problem for a certain temporal logic is PNP[log^2]-complete [Sch03].
For all k ≥ 1, P with logk adaptive queries to NP coincides with P with logk−1 rounds of (polynomially many) nonadaptive queries [CS92].
P-OBDD: Polynomial-Size Ordered Binary Decision Diagram
An ordered binary decision diagram (OBDD) is a branching program (see k-PBP), with the additional constraint that if xi is queried before xj on any path, then i<j.
Then P-OBDD is the class of decision problems solvable by polynomial-size OBDD's.
Contained in PBP, as well as BPP-OBDD.
PODN: Polynomial Odd Degree Node
The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite graph has an even number of odd-degree nodes."
polyL: Polylogarithmic Space
Equals DSPACE((log n)c).
In contrast to L, which is contained in P, it is not known if polyL is contained in P or vice versa (or if none of the inclusions hold). On the other hand, we do know that polyL does not equal P, since (for example) polyL does not have complete problems under many-to-one logspace reductions.
PostBPP: BPP With Postselection
Alias for BPPpath.
PostBPPcc: Communication Complexity PostBPP
The corresponding model consists of randomized protocols that may output 0, 1, or "abort", such that on every input, the non-abort probability is at least some α>0 (which is to be thought of as a function of n), and conditioned on not aborting, the output is correct with probability at least 2/3. The cost of a protocol is defined to be its communication cost plus log(1/α).
Contained in, but does not equal, PPcc [Kla03].
Contained in PHcc.
The complexity measure corresponding to PostBPPcc is equivalent to the "extended discrepancy bound" [GL14].
PostBQP: BQP With Postselection
A class inspired by the proverb, "if at first you don't succeed, try, try again."
Formally, the class of decision problems solvable by a BQP machine such that
- If the answer is 'yes' then the second qubit has at least 2/3 probability of being measured 1, conditioned on the first qubit having been measured 1.
- If the answer is 'no' then the second qubit has at most 1/3 probability of being measured 1, conditioned on the first qubit having been measured 1.
- On any input, the first qubit has a nonzero probability of being measured 1.
Defined in [Aar05b], where it is also shown that PostBQP equals PP.
[Aar05b] also gives the following alternate characterizations of PostBQP (and therefore of PP):
- The quantum analogue of BPPpath.
- The class of problems solvable in quantum polynomial time if we allow arbitrary linear operations (not just unitary ones). Before measuring, we divide all amplitudes by a normalizing factor to make the probabilities sum to 1.
- The class of problems solvable in quantum polynomial time if we take the probability of measuring a basis state with amplitude α to be not |α|2 but |α|p, where p is an even integer greater than 2. (Again we need to divide all amplitudes by a normalizing factor to make the probabilities sum to 1.)
PP: Probabilistic Polynomial-Time
The class of decision problems solvable by an NP machine such that
- If the answer is 'yes' then at least 1/2 of computation paths accept.
- If the answer is 'no' then less than 1/2 of computation paths accept.
Defined in [Gil77].
PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, PPP[log] = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even k-round reductions for any constant k [FR96].
Contains PNP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ2P [Bei94].
BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PPBQP = PP.
APP is PP-low [Li93].
For a random oracle A, PPA is strictly contained in PSPACEA with probability 1 [ABF+94].
For any fixed k, there exists a language in PP that does not have circuits of size nk [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size nk with quantum advice [Aar06] and [Yir24].
By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].
PP can be generalized to the counting hierarchy CH.
PPcc: Communication Complexity PP
Defined in [BFS86], PPcc is one of two ways to define a communication complexity analogue of PP. In PPcc, we note that in an algorithm that uses an amount of random bits bounded by , the bias between the accept and reject probabilities can be no smaller than . Thus, in PPcc, the communication complexity is defined as the sum of the traditional communication complexity (the number of exchanged bits) and the log of the reciprocal of the worst-case (smallest) bias.
The difference between this class and UPPcc is discussed further in [BVW07], where it is shown that PPcc ⊂ UPPcc.
The complexity measure corresponding to PPcc is equivalent to the "discrepancy bound" [Kla07].
See also: UPPcc.
PP/poly: Nonuniform PP
If PP/poly = P/poly then PP is contained in P/poly. Indeed this is true with any syntactically defined class in place of PP. An implication is that any unrelativized separation of BQP/qpoly from BQP/mpoly would imply that PP does not have polynomial-size circuits.
PPA: Polynomial Parity Argument
Defined in [Pap94b]; see also [BCE+95].
The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "all graphs of maximum degree 2 have an even number of leaves."
More precisely, there's a polynomial-time algorithm that, given any string, computes its 'neighbor' strings (of which there are at most two). Then given a leaf string (i.e. one with only one neighbor), the problem is to output another leaf string.
As an example, suppose you're given a cubic graph (one where every vertex has degree 3), and a Hamiltonian cycle H on that graph. Then by making a sequence of modifications to H (albeit possibly exponentially many), it is always possible to find a second Hamilton cycle (see [Pap94]). So this problem is in PPA.
Another problem in PPA is finding an Arrow-Debreu equilibrium, given the goods and utility functions of traders in a marketplace.
Jeřábek [Jeř12] showed that computing the square root mod n and finding quadratic nonresidues mod n are both in PPA. Further, integer factorization is in PPA under the assumption of a generalized Riemann hypothesis.
A complete problem for PPA is Sperner's lemma for non-orientable 3-manifolds. [Gri01]
Contained in TFNP.
Contains PPAD.
There exist oracles relative to which PPA does not contain PLS [BM04] and PPP [BCE+95]. There also exists an oracle relative to which PPA is not contained in PPP [BCE+95].
PPAD: Polynomial Parity Argument (Directed)
Defined in [Pap94b]; see also [BCE+95].
Same as PPA, except now the graph is directed, and we're asked to find either a source or a sink.
NASH, the problem of finding a Nash equilibrium in a normal form game of two or more players with specified utilities, is in PPAD [Pap94b], and proved to be complete for PPAD with four players in [DGP05], and shortly after extended to the case of three players [DP05] and independently [CD05].
There exists an oracle relative to which PPP is not contained in PPAD [BCE+95]. There exists an oracle relative to which PPAD is not contained in BQP [Li11].
PPADS: Polynomial Parity Argument (Directed, Sink)
Defined in [Pap94b]; see also [BCE+95].
Same as PPA, except now the graph is directed, and we're asked to find a sink.
Contained in PPP.
Contains PPAD.
PPP: Polynomial Pigeonhole Principle
Defined in [Pap94b]; see also [BCE+95].
The subclass of TFNP function problems that are guaranteed to have a solution because of the Pigeonhole Principle.
More precisely, we're given a Boolean circuit, that maps n-bit strings to n-bit strings. The problem is to return either an input that maps to 0n, or two inputs that map to the same output.
Contained in TFNP.
Contains PPADS.
[BCE+95] give oracles relative to which PPP is not contained in PPA and PPAD, and PPA is not contained in PPP.
[Mor01] gives an oracle relative to which PPP is not contained in PLS.
[GHJ+22] proves there exists an oracle relative to which PLS is not contained in PPP.
PPP: P With PP Oracle
A level of the counting hierarchy CH.
It is not known whether there exists an oracle relative to which PPP does not equal PSPACE.
Equals P#P (exercise for the visitor).
Since the permanent of a matrix is #P-complete [Val79], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.
PQMA[log]: P With Log QMA Queries
The class of decision problems solvable by a P machine, that can make O(log n) queries to a QMA oracle (where n is the length of the input).
Defined in [Amb14].
Estimating local observables [Amb14], [GY16] and local correlation functions [GY16] against ground states of local Hamiltonians is PQMA[log]-complete.
Estimating local observables remains PQMA[log]-complete even on 2D physical systems and on the 1D line [GPY19].
PQMA[log] is contained in PP [GY16].
P||QMA: P With Parallel Queries To QMA
The class of decision problems solvable by a P machine that can make a polynomial number of non-adaptive queries to a QMA oracle.
PQP: Probabilistic Quantum Polynomial-Time
The class of decision problems solvable in polynomial time by a quantum Turing machine, with less than 1/2 probability of error. Similar to BQP in definition, but without bounded error.
Defined in [Wat09], where it shown to be equivalent to PP.
Equals PP and therefore PPBPP [KST+89b] as well as PostBQP [Aar05b].
PQUERY: PSPACE With Polynomial Queries
The class of decision problems solvable in polynomial space using at most a polynomial number of queries to the oracle.
Thus, PQUERY = PSPACE, but PQUERYA does not equal PSPACEA for some oracles A.
Defined in [Kur83], where it was actually put forward as a serious argument (!!) against believing relativization results.
PPSPACE: Probabilistic PSPACE
Same as IPP, except that IPP uses private coins while PPSPACE uses public coins.
Can also be defined as a probabilistic version of PSPACE.
Equals PSPACE.
Defined in [Pap83].
PR: Primitive Recursive Functions
Basically, the class of functions definable by recursively building up arithmetic functions: addition, multiplication, exponentiation, tetration, etc. What's not allowed is to "diagonalize" a whole series of such functions to produce an even faster-growing one. Thus, the Ackermann function was proposed in 1928 as an example of a recursive function that's not primitive recursive, showing that PR is strictly contained in R.
Alternatively, the PR functions are exactly those functions that can be computed via programs in any reasonable, idealized ALGOL-like programming language where only definite loops are allowed, that is, loops where the number of iterations is specified before the loop starts (so FOR-loops are okay but not WHILE- or REPEAT-loops), and recursive calls are not allowed.
Alternatively, the PR functions are those functions whose termination can be proved by well-founded induction using an ordinal less than ωω. (There are other systems for higher ordinals. Notably, Gödel's System T is an extension of PR with higher-order functions, and it allows all functions whose termination can be proved by well-founded induction using an ordinal less than ε0, including Ackermann's function.)
An interesting difference is that PR functions can be explicitly enumerated, whereas functions in R cannot be (since otherwise the halting problem would be decidable). In this sense, PR is a "syntactic" class whereas R is "semantic."
On the other hand, we can "enumerate" any RE set by a PR function in the following sense: given an input (M,k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M,k), is exactly the set of M that halt.
PR strictly contains ELEMENTARY.
PR: Polynomial-Time Over The Reals
An analog of P for Turing machines over a real number field.
Defined in [BCS+97].
PrHSPACE(f(n)): Unbounded-Error Halting Probabilistic f(n)-Space
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt on every input and every setting of the random tape.
PromiseBPP: Promise-Problem BPP
Same as PromiseRP, but for BPP instead of RP.
Defined in [BF99].
PromiseBQP: Promise-Problem BQP
Same as PromiseBPP, but for BQP instead of BPP.
If PromiseBQP = PromiseP then BQP/mpoly = P/poly.
PromiseP: Promise-Problem P
The class of promise problems solvable by a P machine.
PromiseRP: Promise-Problem RP
The class of promise problems solvable by an RP machine. I.e., the machine must accept with probability at least 1/2 for "yes" inputs, and with probability 0 for "no" inputs, but could have acceptance probability between 0 and 1/2 for inputs that do not satisfy the promise.
Defined in [BF99], where it was also shown that BPP is in RPPromiseRP[1] (i.e. with a single oracle query to PromiseRP).
Contained in PromiseBPP.
PromiseUP: Promise-Problem UP
The class of promise problems solvable by an UP machine. I.e., the nondeterministic machine must have a unique accepting path for "yes" inputs, and no accepting paths "no" inputs, but could have any number of accepting paths for inputs that do not satisfy the promise.
Although not originally stated with this notation, the main result of [VV86] is that NP is contained in RPPromiseUP.
PrSPACE(f(n)): Unbounded-Error Probabilistic f(n)-Space
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt with probability 1 on every input.
Contained in DSPACE(f(n)2) [BCP83].
Equals PrHSPACE(f(n)) [Jun85].
P-Sel: P-Selective Sets
The class of decision problems for which there's a polynomial-time algorithm with the following property. Whenever it's given two instances, a "yes" and a "no" instance, the algorithm can always decide which is the "yes" instance.
Defined in [Sel79], where it was also shown that if NP is contained in P-Sel then P = NP.
There exist P-selective sets that are not recursive (i.e. not in R).
PSK: Polynomial Sink
Yeah, I'm told that's what the S and K stand for. Go figure.
The class of total function problems definable as follows: given a directed graph of indegree and outdegree at most 1, and given a source, find a sink.
Defined in [Pap90].
Equals PPADS.
PSPACE: Polynomial-Space
The class of decision problems solvable by a Turing machine in polynomial space.
Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].
Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].
Contains P#P (P with a #P oracle).
A canonical PSPACE-complete problem is QBF.
Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].
PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.
Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].
In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).
PSPACEcc: Communication Complexity PSPACE
This class is not defined in terms of space, but rather by analogy with the characterization PSPACE=AP. Specifically, a protocol corresponds to a boolean formula where each leaf represents (the indicator function of) a rectangle; the cost of a protocol is the log of the size of the formula.
Contains PHcc.
PSPACE/poly: PSPACE With Polynomial-Size Advice
PT1: Polynomial Threshold Functions
The class of Boolean functions f:{-1,1}n->{-1,1} such that f(x)=sgn(p(x)), where p is a polynomial having a number of terms polynomial in n.
Defined in [BS90], where it was also shown that PT1 contains PL1 (and this inclusion is strict), and that PT1 is contained in PL∞ (and this inclusion is strict).
PTAPE: Archaic for PSPACE
PTAS: Polynomial-Time Approximation Scheme
The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is a polynomial-time algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. (However, the exponent of the polynomial might depend strongly on ε.)
Contains FPTAS, and is contained in APX.
As an example, the Traveling Salesman Problem in the Euclidean plane is in PTAS [Aro96].
Defined in [ACG+99].
PT/WK(f(n),g(n)): Parallel Time f(n) / Work g(n)
The class of decision problems solvable by a uniform family of Boolean circuits with depth upper-bounded by f(n) and size (number of gates) upper-bounded by g(n).
The union of PT/WK(logkn, nk) over all constants k equals NC.
PZK: Perfect Zero Knowledge
Same as SZK, but now the two distributions must be identical, not merely statistically close. (The "two distributions" are (1) the distribution over the verifier's view of his interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)
Contained in SZK and HVPZK. There are oracles separating PZK from SZK, coPZK, NIPZK, and coSBP. [BCHTV17], [DGPV20].
See also: CZK.