Complexity Zoo:P

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] - P_CTC - PAC⁰ - PBP - k-PBP - P_C - P^cc - P_$k$^cc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PDQP - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PH^cc - Φ₂P - PhP - Π₂P - PINC - PIO - P^K - PKC - PL - PL₁ - PL_∞ - PLF - PLL - P-LOCAL - P-RLOCAL - PLS - P^NP - P^NPcc - P^||NP - P^NP[k] - P^NP[log] - P^{NP[log^2]} - P-OBDD - PODN - polyL - PostBPP - PostBPP^cc - PostBQP - PP - PP^cc - PP/poly - PPA - PPAD - PPADS - P^PP - PPP - PPSPACE - P^QMA[log] - PQUERY - PR - P_R - Pr_HSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACE^cc - PSPACE/poly - PT₁ - 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 P_R and P_C respectively.

In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO($n^{O(1)}$)], 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, Σ₂P.

They also showed:

• If PSPACE is in P/poly then PSPACE equals Σ₂P ∩ Π₂P.
• If EXP is in P/poly then EXP = Σ₂P.

It was later shown that, if NP is contained in P/poly, then PH collapses to ZPP^NP [KW98] and indeed to O₂P [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 Δ₂P [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 Σ₂P 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 P^PP (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].

---

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

See also BQP_CTC.

---

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.

---

PAC⁰: Probabilistic AC⁰

The Political Action Committee for computational complexity research.

The class of problems for which there exists a DiffAC⁰ function f such that the answer is "yes" on input x if and only if f(x)>0.

Equals TC⁰ and C₌AC⁰ under logspace uniformity [ABL98].

---

PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Equals L/poly [Cob66].

Contains P-OBDD, BP_d(P).

---

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) NC¹ for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC⁰ [BT88].

Contained in k-EQBP, as well as PBP.

See also BP_d(P).

---

P_C: Polynomial-Time Over The Complex Numbers

An analog of P for Turing machines over a complex number field.

Defined in [BCS+97].

See also P_R, NP_C, NP_R, VP_k.

---

P^cc: 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. P^cc 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 $O(n)$ 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 NP^cc and in BPP^cc because of the EQUALITY problem.

If the classes are defined in terms of total functions, then P^cc = NP^cc ∩ coNP^cc = UP^cc.

Defined in [BFS86].

---

P_$k$^cc: P^cc in NOF model, $k$ players

Like P^cc, but with $k$ 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, P_$k$^cc is the class of functions $F:X_{1}\times X_{2}\times \cdots \times X_{k}\to \{0,1\}$ where for all $i\in [1..k]$, $X_{k}\in \{0,1\}^{n}$, such that $F$ is solvable in a deterministic sense by $k$ players, each of which is aware of all inputs $X_{i}$ other than his own, and such that $O\left(\mathrm {poly} (\log n)\right)$ bits of communication are used.

P_$k$^cc is trivially contained in BPP_$k$^cc, RP_$k$^cc and NP_$k$^cc.

---

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:

1. If the answer is "yes," there exists a proof such that the verifier accepts with certainty.
2. 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(2^O(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].

---

---

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 Δ₀P = Σ₀P = Π₀P = P. Then for i>0, let

• Δ_iP = P with Σ_i-1P oracle.
• Σ_iP = NP with Σ_i-1P oracle.
• Π_iP = coNP with Σ_i-1P oracle.

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

Contains BPP [Lau83].

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 ${\mathsf {P}}^{\mathrm {SAT} [1]}={\mathsf {P}}^{\mathrm {SAT} [2]}\Rightarrow {\mathsf {PH}}\subseteq {\mathsf {NP}}$.

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.

---

PH^cc: Communication Complexity PH

The polynomial hierarchy for communication complexity, naturally built with NP^cc and coNP^cc forming the first level. Specifically, a cost-k protocol in the PH^cc model corresponds to a constant-depth 2^k-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 Σ₂^cc equals Π₂^cc.

Defined in [BFS86], where it was also shown (among other things) that BPP^cc is contained in Σ₂^cc ∩ Π₂^cc.

---

Φ₂P: 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

1. For all y, there exists a z for which P(x,y,z).
2. For all z, there exists a y for which P(x,y,z).

Contained in Σ₂P and Π₂P.

Defined in [Can96], where it was also observed that Φ₂P = S₂P.

---

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(n¹⁰⁰⁰) into PhP than BQTIME(n²). 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 10^k with k in the low hundreds.) In practice, less than 10⁵⁰ bits and less than 10⁸⁰ 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.

---

Π₂P: coNP With NP Oracle

Complement of Σ₂P.

Along with Σ₂P, comprises the second level of PH, the polynomial hierarchy. For any fixed k, there is a problem in Π₂P ∩ Σ₂P that cannot be solved by circuits of size n^k [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}ⁿ->{0,1}^m, such that the k^th output bit is computable in time polynomial in n and k.

Defined in [JY88].

Contained in PIO. This containment is strict, since if m=2ⁿ (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}ⁿ->{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.

---

P^K: 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 P^K contains PSPACE. It is not known whether P^K contains all of R, or even any recursive problem not in PSPACE.

See also: BPP^KT.

---

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

PL^PL = PL (see [HO02]).

---

PL₁: Polynomially-Bounded L₁ Spectral Norm

The class of Boolean functions f:{-1,1}ⁿ->{-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 PL₁ is contained in PT₁ (and this inclusion is strict).

---

PL_∞: Polynomially-Bounded L_∞^-1 Spectral Norm

The class of Boolean functions f:{-1,1}ⁿ->{-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 PT₁ (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].)

Defined in [JPY88], [PY88].

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.

---

P^NP: P With Oracle Access To NP

See Δ₂P.

---

P^NPcc: Communication Complexity P^NP

Not contained in PP^cc [BVW07].

Does not contain BPP^cc if partial functions are allowed [PPS14].

Contained in UPostBPP^cc.

---

P^||NP: P With Parallel Queries To NP

Equals P^NP[log] ([BH91] and [Hem89] independently).

---

P^NP[k]: P With k NP Queries(for constant k)

Equals P with 2^k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).

If P^NP[1] = P^NP[2], then P^NP[1] = P^NP[log] and indeed PH collapses to Δ₃P (attributed in [Har87b] to J. Kadin).

---

P^NP[log]: P With Log NP Queries

Also known as Θ₂^P.

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

P^NP[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 P^NP[log] [HHR97].

Contains P^NP[k] for all constants k.

---

P^{NP[log^2]}: P With Log² NP Queries

Same as P^NP[log], except that now log² queries can be made.

The model-checking problem for a certain temporal logic is P^{NP[log^2]}-complete [Sch03].

For all k ≥ 1, P with log^k adaptive queries to NP coincides with P with log^k−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 x_i is queried before x_j 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."

Equals PPA [Pap90].

---

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

---

PostBPP^cc: 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, PP^cc [Kla03].

Contained in PH^cc.

The complexity measure corresponding to PostBPP^cc 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 BPP_path.
• 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 |α|² 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

1. If the answer is 'yes' then at least 1/2 of computation paths accept.
2. 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, P^PP[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 P^NP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ₂P [Bei94].

PH is in P^PP [Tod89].

BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PP^BQP = PP.
APP is PP-low [Li93].

Equals PostBQP [Aar05b].

For a random oracle A, PP^A is strictly contained in PSPACE^A with probability 1 [ABF+94].

For any fixed k, there exists a language in PP that does not have circuits of size n^k [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size n^k 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.

---

PP^cc: Communication Complexity PP

Defined in [BFS86], PP^cc is one of two ways to define a communication complexity analogue of PP. In PP^cc, we note that in an algorithm that uses an amount of random bits bounded by $c$, the bias between the accept and reject probabilities can be no smaller than $2^{c}$. Thus, in PP^cc, 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 UPP^cc is discussed further in [BVW07], where it is shown that PP^cc ⊂ UPP^cc.

The complexity measure corresponding to PP^cc is equivalent to the "discrepancy bound" [Kla07].

See also: UPP^cc.

---

PP/poly: Nonuniform PP

Contains BQP/qpoly [Aar04b].

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.

Contained in PPA and PPADS.

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 0ⁿ, 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.

---

P^PP: P With PP Oracle

A level of the counting hierarchy CH.

It is not known whether there exists an oracle relative to which P^PP does not equal PSPACE.

Contains PP^PH [Tod89].

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.

---

P^QMA[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].

Equals P^||QMA [GPY19].

Estimating local observables [Amb14], [GY16] and local correlation functions [GY16] against ground states of local Hamiltonians is P^QMA[log]-complete.

Estimating local observables remains P^QMA[log]-complete even on 2D physical systems and on the 1D line [GPY19].

P^QMA[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.

Equals P^QMA[log] [GPY19].

---

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 PP^BPP [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 PQUERY^A does not equal PSPACE^A 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 ε₀, 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.

---

P_R: Polynomial-Time Over The Reals

An analog of P for Turing machines over a real number field.

Defined in [BCS+97].

See also P_C, NP_C, NP_R, VP_k.

---

Pr_HSPACE(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.

Equals PrSPACE(f(n)) [Jun85].

---

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 RP^PromiseRP[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 RP^PromiseUP.

---

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)²) [BCP83].

Equals Pr_HSPACE(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($2^{n^{O(1)}}$) which is also FO(PFP) and SO($n^{O(1)}$) which is also SO(TC).

---

PSPACE^cc: 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 PH^cc.

---

PSPACE/poly: PSPACE With Polynomial-Size Advice

Contains QMA/qpoly [Aar06b].

---

PT₁: Polynomial Threshold Functions

The class of Boolean functions f:{-1,1}ⁿ->{-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 PT₁ contains PL₁ (and this inclusion is strict), and that PT₁ is contained in PL_∞ (and this inclusion is strict).

---

---

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(log^kn, n^k) 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.