Complexity Zoo:P

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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 an '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 S2P [Cai01]. 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.

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

Equals PPP (exercise for the visitor).

P#P[1]: P With Single Query To #P Oracle

Contains PH [Tod89].

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.

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.

Equals L/poly [Cob66].

Contains P-OBDD, BPd(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) 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.

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 $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 NPcc and in BPPcc because of the EQUALITY problem.

If the classes are defined in terms of total functions, then Pcc = NPcccoNPcc = UPcc.

Defined in [BFS86].

P$k$cc: Pcc in NOF model, $k$ players

Like Pcc, 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(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.

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 Δ0P = Σ0P = Π0P = 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 constant 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.

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

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 Σ2P and Π2P.

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.