Class Description

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

Linked From

0-1-NP_C: Binary Restriction of NP Over The Complex Numbers

The intersection of NP_C with {0,1}^* (i.e. the set of binary strings).

Contains NP.

Is contained in PSPACE, and in AM assuming the Extended Riemann Hypothesis [Koi96].

More about...

ALL: The Class of All Languages

Literally, the class of ALL languages.

ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.

First [Aar04b] observed that PP/rpoly (PP with polynomial-size randomized advice) equals ALL, as does PostBQP/qpoly (PostBQP with polynomial-size quantum advice).

Then [Raz05] showed that QIP/qpoly, and even IP(2)/rpoly, equal ALL.

Nor is it hard to show that MA_EXP/rpoly = ALL.

Also, per [Aar18], PDQP/qpoly = ALL.

On the other hand, even though PSPACE contains PP, and EXPSPACE contains MA_EXP, it's easy to see that PSPACE/rpoly = PSPACE/poly and EXPSPACE/rpoly = EXPSPACE/poly are not ALL.

So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)

It is not as contradictory as it first seems. The deterministic base class in all of these examples is modified by computational non-determinism after it is modified by advice. For example, MA_EXP/rpoly means M(A_EXP/rpoly), while (MA_EXP)/rpoly equals MA_EXP/poly by a standard argument. In other words, it's only the verifier, not the prover or post-selector, who receives the randomized or quantum advice. The prover knows a description of the advice state, but not its measured values. Modification by /rpoly does preserve class inclusions when it is applied after other changes.

More about...

Almost-PSPACE: Languages Almost Surely in PSPACE^A

The class of problems that are in PSPACE^A with probability 1, where A is an oracle chosen uniformly at random.

Almost-PSPACE is not known to equal PSPACE -- rather surprisingly, given the fact that PSPACE equals BPPSPACE and even PPSPACE.

What's known is that Almost-PSPACE = BP^exp⋅PSPACE, where BP^exp⋅ is like the BP⋅ operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXP^NP ∩ coNEXP^NP.

Whereas both BP^exp⋅PSPACE and BPPSPACE machines are allowed exponentially many random bits, the former has a reusable record of all of these bits on a witness tape, while the latter can only preserve a fraction of them on the work tape.

More about...

AP: Alternating P

An alternating Turing machine is a nondeterministic machine with two kinds of states, AND states and OR states. It accepts if and only if the tree of all computation paths, considered as an AND-OR tree, evaluates to 1. (Here 'Accept' corresponds to 1 and 'Reject' to 0.)

Then AP is the class of decision problems solvable in polynomial time by an alternating Turing machine.

AP = PSPACE [CKS81].

The abbreviation AP is also used for Approximable in Polynomial Time, see AxP.

More about...

APSPACE: Alternating PSPACE

APSPACE is the class of decision problems solvable with polynomial space by an alternating Turing machine. See also ASPACE.

APSPACE = EXP [CKS81].

More about...

AUC-SPACE(f(n)): Randomized Alternating f(n)-Space

The class of problems decidable by an O(f(n))-space Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Contains GAN-SPACE(f(n)).

AUC-SPACE(poly(n)) = SAPTIME = PSPACE [Pap83].

[Con92] shows that AUC-SPACE(log n) has a natural complete problem, and is contained in NP ∩ coNP.

More about...

AW[SAT]: Alternating W[SAT]

Basically has the same relation to W[SAT] as PSPACE does to NP.

The class of decision problems of the form (x,r,k₁,...,k_r) (r,k₁,...,k_r parameters), that are fixed-parameter reducible to the following problem, for some constant h:

Parameterized QBFSAT: Given a Boolean formula F (with no restriction on depth), over disjoint variable sets S₁,...,S_r. Does there exist an assignment to S₁ of Hamming weight k₁, such that for all assignments to S₂ of Hamming weight k₂, etc. (alternating 'there exists' and 'for all'), F is satisfied?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains AW[*], and is contained in AW[P].

More about...

AW[t]: Alternating W[t]

Has the same relation to W[t] as PSPACE does to NP.

Same as AW[SAT], except that the formula F can have depth at most t.

Defined in [DF99].

Contained in AW[*].

[DFT98] show that for all t, AW[t] = AW[*].

More about...

BPP//log: BPP With Logarithmic Randomness-Dependent Advice

The class of problems solvable by a BPP machine that is given O(log n) advice bits, which can depend on both the machine's random coin flips and the input length n, but not on the input itself.

Defined in [TV02], where it was also shown that if EXP is in BPP//log thenEXP = BPP, and if PSPACE is in BPP//log then PSPACE = BPP.

More about...

BQPSPACE: Bounded-Error Quantum PSPACE

Equals PSPACE and PPSPACE.

More about...

CH: Counting Hierarchy

The union of the C_kP's over all constant k.

Contained in PSPACE.

Strictly contains DLOGTIME-uniform TC⁰ [CMTV98].

It is an open problem whether there exists an oracle relative to which CH is infinite, or even unequal to PSPACE. This is closely related to the problem of whether TC⁰ = NC¹, since a padding argument shows that TC⁰ = NC¹ implies CH = PSPACE.

More about...

compIP: Competitive IP Proof System

Same as compNP but for interactive (IP) proofs instead of NP proofs.

More formally, compIP is the class of decision problems L in IP = PSPACE such that, if the answer is "yes," then that can be proven by an interactive protocol between a BPP verifier and a prover, a BPP machine with access only to an oracle for L.

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in compIP [BG94].

More about...

CZK: Computational Zero-Knowledge

Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don't have to be statistically close. (The "two distributions" are (1) the distribution over the verifier's view of their 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.)

Unlike SZK, it is not known if CZK is closed under complement. CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions [GMW91].)

Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).

On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].

Contains PZK and SZK.

More about...

E: Exponential Time With Linear Exponent

Equals DTIME(2^O(n)).

Does not equal NP [Boo72] or PSPACE [Boo74] relative to any oracle. However, there is an oracle relative to which E is contained in NP (see ZPP), and an oracle relative to PSPACE is contained in E (by equating the former with P).

There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [Wat87].

Problems hard for BPP under Turing reductions have measure 1 in E [AS94].

It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then BPP does not equal EXP.

[IT89] gave an oracle relative to which E = NE but still there is an exponential-time binary predicate whose corresponding search problem is not in E.

[BF03] gave a proof that if E = NE, then no sparse set is collapsing, where they defined a set ${\displaystyle A}$ to be collapsing if ${\displaystyle A\notin {\mathsf {P}}}$ and if for all ${\displaystyle B}$ such that ${\displaystyle A}$ and ${\displaystyle B}$ are Turing reducible to each other, ${\displaystyle A}$ and ${\displaystyle B}$ are many-to-one reducible to each other.

Contrast with EXP.

More about...

EXP: Exponential Time

Equals the union of DTIME(2^p(n)) over all polynomials p.

Also equals P with E oracle.

If L = P then PSPACE = EXP.

If EXP is in P/poly then EXP = MA [BFL91].

Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].

There exist oracles relative to which

• EXP = NP = ZPP [Hel84a], [Hel84b], [Hel86],
• EXP = NEXP but still P does not equal NP [Dek76],
• EXP does not equal PSPACE [Dek76].

[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.

[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MA_POLYLOG such that no deterministic polynomial-time adversary can generate a list of inputs for a P problem that includes one which fails to be simulated. As a result, EXP ⊆ MA if EXP has circuits of polynomial size.

[SU05] show that EXP ${\displaystyle \not \subseteq }$ NP/poly implies EXP ${\displaystyle \not \subseteq }$ P^||NP/poly.

In descriptive complexity EXPTIME can be defined as SO(${\displaystyle 2^{n^{O(1)}}}$) which is also SO(LFP)

More about...

FO: First-Order logic

First order logic is the smallest logical class of logic language. It is the base of Descriptive complexity and equal to the class AC⁰.

When we use logic formalism, the input is a structure, usually it is either strings (of bits or over an alphabet) whose elements are position of the strings, or graphs whose elements are vertices. The measure of the input will there be the size of the structure.Whatever the structure is, we can suppose that there are relation that you can test, by example ${\displaystyle E(x,y)}$ is true iff there is an edge from ${\displaystyle x}$ to ${\displaystyle y}$ if the structure is a graph, and ${\displaystyle P(n)}$ is true iff the nth letter of the string is 1. We also have constant, who are special elements of the structure, by example if we want to check reachability in a graph, we will have to choose two constant s and t.

In descriptive complexity we almost always suppose that there is a total order over the elements and that we can check equality between elements. This let us consider elements as number, ${\displaystyle x}$ is the number ${\displaystyle n}$ iff there is ${\displaystyle (n-1)}$ elements ${\displaystyle y}$ such that ${\displaystyle y<x}$. Thanks to this we also want the primitive "bit", where ${\displaystyle bit(x,y)}$ is true if only the ${\displaystyle y}$th bit of ${\displaystyle x}$ is 1. (We can replace ${\displaystyle bit}$ by plus and time, ternary relation such that ${\displaystyle plus(x,y,z)}$ is true iff ${\displaystyle x+y=z}$ and ${\displaystyle times(x,y,z)}$ is true iff ${\displaystyle x*y=z}$).

Since in a computer elements are only pointers or string of bits, those assumptions make sense, and those primitive functions can be calculated in most of the small complexity classes. We can also imagine FO without those primitives, which gives us smaller complexity classes.

The language FO is then defined as the closure by conjunction ( ${\displaystyle \wedge }$), negation (${\displaystyle \neg }$) and universal quantification (${\displaystyle \forall }$) over element of the structures. We also often use existential quantification (${\displaystyle \exists }$) and disjunction (${\displaystyle \vee }$) but those can be defined thanks to the 3 first symbols.

The semantics of the formulae in FO is straightforward, ${\displaystyle \neg A}$ is true iff ${\displaystyle A}$ is false, ${\displaystyle A\wedge B}$ is true iff ${\displaystyle A}$ is true and ${\displaystyle B}$ is true, and (${\displaystyle \forall xP}$) is true iff whatever element we decide that ${\displaystyle x}$ is we can choose, ${\displaystyle P}$ is true.

A query in FO will then be to check if a FO formulae is true over a given structure, this structure is the input of the problem. One should not confuse this kind of problem with checking if a quantified boolean formula is true, which is the definition of QBF, which is PSPACE-complete. The difference between those two problem is that in QBF the size of the problem is the size of the formula and elements are just boolean value, whereas in FO the size of the problem is the size of the structure and the formula is fixed.

Every formulae is equivalent to a formulae in prenex normal form where we put recursively every quantifier and then a quantifier-free formulae.

More about...

FO(PFP): First-order with partial fixed point

FO(pfp) is the set of boolean queries definable with first-order formulae with a partial fixed point operator.

Let ${\displaystyle k}$ be an integer, ${\displaystyle x,y}$ vectors of ${\displaystyle k}$ variables, ${\displaystyle P}$ a second-order variable of arity ${\displaystyle k}$, and ${\displaystyle \phi }$ a FO(PFP) function using ${\displaystyle x}$ and ${\displaystyle P}$ as variables, then we can define iteratively ${\displaystyle (P_{i})_{i\in N}}$ such that ${\displaystyle P_{0}(x)=false}$ and ${\displaystyle P_{i}(x)=\phi (P_{i-1},x)}$ which means that the property ${\displaystyle P_{i}}$ is true on the input ${\displaystyle x}$ if ${\displaystyle \phi }$ is true on input ${\displaystyle x}$, and when the variable ${\displaystyle P}$ is replaced by ${\displaystyle P_{i-1}}$. Then, either there is a fixed point, or the list of ${\displaystyle (P_{i})}$ is looping.

PFP(${\displaystyle \phi _{P,x})(y)}$ is defined as the value of the fixed point of ${\displaystyle (P_{i})}$ on y if there is a fixed point, else as false.

Since ${\displaystyle P}$s are property of arity ${\displaystyle k}$, there is at most ${\displaystyle 2^{n^{k}}}$ values for the ${\displaystyle P_{i}}$s, so with a poly-space counter we can check if there is a loop or not.

It was proved in [Imm98] that FO(pfp) is equal to PSPACE.

More about...

FO[${\displaystyle t(n)}$]: Iterated First-Order logic

Let ${\displaystyle t(n)}$ be a function from integers to integers.${\displaystyle (\forall xP)Q}$ abbreviates ${\displaystyle (\forall x(P\Rightarrow Q))}$ and ${\displaystyle (\exists xP)Q}$ abbreviates ${\displaystyle (\exists x(P\wedge Q))}$.

A quantifier block is a list ${\displaystyle (Q_{1}x_{1}.\phi _{1})...(Q_{k}x_{k}.\phi _{k})}$ where the ${\displaystyle \phi _{i}}$s are quantifier free FO-formulae and each ${\displaystyle Q_{i}}$s is either ${\displaystyle \forall }$ or ${\displaystyle \exists }$.If ${\displaystyle Q}$ is a quantifier block then ${\displaystyle [Q]^{t(n)}}$ is the block consisting of ${\displaystyle t(n)}$ iterated copies of ${\displaystyle Q}$. Note that there are ${\displaystyle k*t(n)}$ quantifiers in the list, but only k variables; each variable is used ${\displaystyle t(n)}$ times.

FO[${\displaystyle t(n)}$] consists of the FO-formulae with quantifier blocks that are iterated ${\displaystyle \Theta (t(n))}$ times.

In Descriptive complexity we can see that :

• FO[${\displaystyle (\log n)^{i}}$] is equal to fo-uniform ACⁱ, and in fact FO[${\displaystyle t(n)}$] is fo-uniform AC of depth ${\displaystyle t(n)}$
• FO[${\displaystyle (\log n)^{O(1)}}$] is equal to NC
• FO[${\displaystyle n^{O(1)}}$] is equal to P and FO(LFP)
• FO[${\displaystyle 2^{n^{O(1)}}}$] is equal to PSPACE and FO(PFP)

More about...

IP: Interactive Proof Systems

The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:

1. If the answer is "yes," the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier's random bits).
2. If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.

Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness.However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).

First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown thatIP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].

The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.

See also: MIP, QIP, MA, AM.

More about...

IPP: Unbounded IP

Same as IP, except that if the answer is "yes," there need only be a prover strategy that causes the verifier to accept with probability greater than 1/2, while if the answer is "no," then for all prover strategies the verifier accepts with probability less than 1/2.

Defined in [CCG+94], where it was also shown that IPP = PSPACE relative to all oracles. Since IP is strictly contained in PSPACE relative to a random oracle, the authors interpreted this as evidence against the Random Oracle Hypothesis (a slight change in definition can cause the behavior of a class relative to a random oracle to change drastically).

See also: PPSPACE.

More about...

MIP^ns: MIP with Non-Signaling Provers

Same as MIP, except that the provers can have non-signaling strategies.

MIP^ns with two provers is equal to PSPACE [Ito10]. MIP^ns with polylogarithmically many provers is equal to EXP [KRR13].

More about...

(M_k)P: Acceptance Mechanism by Monoid M_k

A monoid is a set with an associative operation and an identity element (so it's like a group, except that it need not have inverses).

Then (M_k)P is the class of decision problems solvable by an NP machine with the following acceptance mechanism. The i^th computation path (under some lexicographic ordering) outputs an element m_i of M_k. Then the machine accepts if and only if m₁m₂...m_s is the identity (where s is the number of paths).

Defined by Hertrampf [Her97], who also showed the following (in the special case M is a group):

• If G is any nonsolvable group (for example S₅, the symmetric group on 5 elements), then (G)P = PSPACE.
• (Z_k)P = coMod_kP, where Z_k is the cyclic group on k elements.
• If |G|=k, then (G)P contains coMod_kP.

More about...

NPSPACE: Nondeterministic PSPACE

Equals PSPACE [Sav70].

On the other hand, this result does not relativize if we allow strings of unbounded length to be written to the oracle tape. In particular, there exists an oracle relative to which NPSPACE is not contained in EXP [GTW+91].

More about...

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.

More about...

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

More about...

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

More about...

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${\displaystyle {\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.

More about...

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.

More about...

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.

More about...

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.

More about...

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.

More about...

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

More about...

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.

More about...

PSPACE/poly: PSPACE With Polynomial-Size Advice

Contains QMA/qpoly [Aar06b].

More about...

PTAPE: Archaic for PSPACE

More about...

QAM: Quantum AM

The class of decision problems for which a "yes" answer can be verified by a public-coin quantum AM protocol, as follows. Arthur generates a uniformly random (classical) string and sends it to Merlin. Merlin responds with a polynomial-size quantum certificate, on which Arthur can perform any BQP operation. The completeness and soundness requirements are the same as for AM.

Defined by Marriott and Watrous [MW05].

Contains QMA and is contained in QIP[2] and BP•PP (and therefore PSPACE).

More about...

QIP: Quantum IP

The class of decision problems such that a "yes" answer can be verified by a quantum interactive proof. Here the verifier is a BQP (i.e. quantum polynomial-time) algorithm, while the prover has unbounded computational resources (though cannot violate the linearity of quantum mechanics). The prover and verifier exchange a polynomial number of messages, which can be quantum states. Thus, the verifier's and prover's states may become entangled during the course of the protocol. Given the verifier's algorithm, we require that

1. If the answer is "yes," then the prover can behave in such a way that the verifier accepts with probability at least 2/3.
2. If the answer is "no," then however the prover behaves, the verifier rejects with probability at least 2/3.

Let QIP[k] be QIP where the prover and verifier are restricted to exchanging k messages (with the prover going last).

Defined in [Wat99], where it was also shown that PSPACE is in QIP[3].

Subsequently [KW00] showed that for all k>3, QIP[k] = QIP[3] = QIP.

QIP is contained in EXP [KW00].

QIP = IP = PSPACE [JJUW09]; thus quantum computing adds no power to single-prover interactive proofs.

QIP(1) is more commonly known as QMA.

See also: QIP[2], QSZK.

More about...

QMA(2): Quantum MA With Multiple Certificates

Same as QMA, except that now the verifier is given two polynomial-size quantum certificates, which are guaranteed to be unentangled.

Defined in [KMY01].

In [BT09], the authored presented a QMA_log(2) (that is, the length of the certificates is logarithmic in the size of the problem -- see, e.g., QMA_log) protocol for 3-Coloring, with perfect completeness and 1-1/poly(n) soundness. Note that a similar construction for QMA is highly unlikely, since it would imply NP is contained in QMA_log=BQP. An analogous result, with constant soundness but with quadratic proof length was shown in [ABD+08]. It was shown shown there that a conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE. The authors also show that there exists no perfectly disentangler that can be used to simulate QMA(2) in QMA, though other approaches to showing QMA = QMA(2) may still exist.

It was shown in [HM13] that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. It was shown in [BCY11] that QMA(2) = QMA if the verifier is restricted to one-way LOCC protocols.

The best known unconditional upper bound is NEXP. If QMA(2)=NEXP, then QΣ₂=QΠ₂ (see QPH) (alternating quantifiers provide no additional power in the quantum setting) [GSSSY18]. If QCPH=QPH (quantum proofs provide no additional power in the presence of alternating quantifiers), then QMA(2) is in P^PPPP [GSSSY18].

Approximating the minimal energy of a sparse Hamiltonian with respect to a separable state (which is known as the Separable Sparse Hamiltonian problem) is QMA(2)-complete [CS12]. This is in contrast to the Separable Local Hamiltonian problem which is in QMA [CS12].

More about...

QMAM: Quantum Merlin-Arthur-Merlin Public-Coin Interactive Proofs

The class of decision problems for which a "yes" answer can be verified by a public-coin quantum MAM protocol, as follows. Merlin sends a polynomial-size quantum state to Arthur. Arthur then flips some classical coins (in fact, he only has to flip one without loss of generality) and sends the outcome to Merlin. At this stage Arthur is not yet allowed to perform any quantum operations. Merlin then sends Arthur another quantum state. Finally, Arthur performs a BQP operation on both of the states simultaneously, and either accepts or rejects. The completeness and soundness requirements are the same as for AM. Also, Merlin's messages might be entangled.

Defined by Marriott and Watrous [MW05], who also showed that QMAM = QIP(3) = QIP.

Hence QMAM equals PSPACE.

More about...

QRG(k): k-turn Quantum Refereed Games

Same as QRG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. QRG(k) is the quantum version of RG(k). By definition, QRG(poly) = QRG. See also QRG(1) and QRG(2).

QRG(k) trivially contains RG(k) for each k (and hence PSPACE when ${\displaystyle k\geq 2}$). QRG(4) trivially contains SQG.

QRG(k) is trivially contained in QRG for each k (and hence EXP).

Other than these trivial bounds, very little is known of QRG(k) for intermediate values of k. For example, does QRG(k) = RG(k) for each k?

More about...

QRG(2): Two-turn (one-round) Quantum Refereed Games

Same as QRG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. QRG(2) is the quantum version of RG(2). See also QRG(k).

QRG(2) trivially contains RG(2) (and hence PSPACE).

QRG(2) is trivially contained in SQG (and hence PSPACE). Hence QRG(2) = RG(2) = PSPACE and finding optimal strategies for two-turn zero-sum quantum games is no harder than finding optimal strategies for two-turn zero-sum classical games.

More about...

QRG(1): One-turn Quantum Refereed Games

The class of problems for which there exists a BQP machine M such that:

• If the answer is "yes," then there exists a quantum state ρ such that for all quantum states σ, M(ρ,σ) accepts with probability at least 2/3.
• If the answer is "no," then there exists a σ such that for all ρ, M(ρ,σ) rejects with probability at least 2/3.

In other words, it's the same as QRG(k) for ${\displaystyle k=1}$, the class of problems that admit quantum interactive proofs with competing provers in which there's no communication from the verifier back to the provers. QRG(1) is the quantum version of RG(1).

Defined in [JW09], where it was shown that QRG(1) is contained in PSPACE .

QRG(1) trivially contains QMA (and indeed P^QRG(1)).

QRG(1) is trivially contained in QRG(2) (and hence PSPACE).

More about...

QSZK: Quantum Statistical Zero-Knowledge

A quantum analog of SZK (or more precisely HVSZK).

Arthur is a BQP (i.e. quantum) verifier who can exchange quantum messages with Merlin. So Arthur and Merlin's states may become entangled during the course of the protocol.

Arthur's "view" of his interaction with Merlin is taken to be the sequence of mixed states he has, over all steps of the protocol. The zero-knowledge requirement is that each of these states must have trace distance at most (say) 1/10 from a state that Arthur could prepare himself (in BQP), without help from Merlin. Arthur is assumed to be an honest verifier.

Defined in [Wat02], where the following was also shown:

• QSZK is contained in PSPACE.
• QSZK is closed under complement.
• Any protocol can be parallelized to consist of two messages, so that QSZK is in QIP[2].
• One can assume without loss of generality that protocols are public-coin, as for SZK.
• QSZK has a natural complete promise problem, called Quantum State Distinguishability (QSD). We are given quantum circuits Q₀ and Q₁. Let ρ₀ and ρ₁ be the mixed states they produce respectively, when run on the all-0 state (and when non-output qubits are traced out). We are promised that the trace distance between ρ₀ and ρ₁ is either at most α or at least β, where α and β are constants in [0,1] satisfying α < β². The problem is to decide which of these is the case.

Subsequently, [Wat09b] showed that honest-verifier and general-verifier quantum statistical zero-knowledge are equivalent.

There exists an oracle relative to which QSZK does not contain UP ∩ coUP, and a random oracle relative to which QSZK does not contain UP [MW18].

More about...

RG: Refereed Games

The class of problems solvable by a probabilistic polynomial-time verifier who can exchange a polynomial number of messages with two competing, computationally-unbounded provers -- one trying to convince the verifier that the answer is "yes," the other that the answer is "no." Note that the verifier can hide information from the provers. Public-coin RG amounts to SAPTIME, which equals PSPACE [Pap83].

RG is in EXP relative to any oracle [KM92]; they are equal, unrelativized [FK97b].

See also PCD, GPCD.

More about...

RG(k): k-turn Refereed Games

Same as RG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. By definition, RG(poly) = RG. See also RG(1) and RG(2).

Other than trivial bounds, very little is known of RG(k) for intermediate values of k. For example, does RG(k) = PSPACE for each constant ${\displaystyle k\geq 2}$?

More about...

RG(2): Two-turn (one-round) Refereed Games

Same as RG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. See also RG(k).

RG(2) is contained in PSPACE, and they are equal, unrelativized [FK97b].

More about...

RG(1): One-turn Refereed Games

The class of problems for which there exists a BPP machine M such that, on input x:

1. If the answer is 'yes,' then there exists a distribution Y such that for all distributions Z, M(x,Y,Z) accepts with probability at least 2/3.
2. If the answer is 'no,' then there exists a distribution Z such that for all distributions Y, M(x,Y,Z) rejects with probability at least 2/3.

In other words, it's the same as RG(k) for ${\displaystyle k=1}$, the class of problems that admit interactive proofs with competing provers in which there's no communication from the verifier back to the provers.

RG(1) trivially contains S₂P. Indeed, RG(1) can be viewed as a randomized version of S₂P.

RG(1) is trivially contained in RG(2) (and hence PSPACE).

More about...

SAPTIME: Stochastic Alternating Polynomial-Time

The class of problems solvable by a polynomial-time Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Defined in [Pap83], where it was also observed that SAPTIME = PSPACE.

More about...

SF_k: Width-k Bottleneck Turing Machines

The class of decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF₂ contains both ⊕P and NP by using the counter as a witness.

Defined in [CF91], where it was also shown that SF₅ = PSPACE.

The complexity of SF₂, SF₃, and SF₄ was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:

(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)

More about...

SLICEWISE PSPACE: Parametrized PSPACE

The parameterized version of PSPACE.

Same as FPT, except that now on input (x,k) (k a parameter), the space used must be f(k)p(|x|), where p is a polynomial.

If P = PSPACE, then FPT = SLICEWISE PSPACE.

Defined in [DF99].

More about...

SO[TC]: Second-Order logic with transitive closure

SO[TC] is to SO as FO[TC] is to FO. The TC operator can now also take second-order variable as argument.

In Descriptive complexity we can see thatSO[TC] is equal to PSPACE.

More about...

SO[${\displaystyle t(n)}$]: Iterated Second-Order logic

SO[${\displaystyle t(n)}$] is to SO as FO[${\displaystyle t(n)}$] is to FO. But we now also have second-order quantifier in the quantifier block.

In Descriptive complexity we can see that :

• SO[${\displaystyle n^{O(1)}}$] is equal to PSPACE it is also another way to write SO(TC)
• SO[${\displaystyle 2^{n^{O(1)}}}$] is equal to EXPTIME it is also another way to write SO(LFP)

More about...

SQG: Short Quantum Games

Same as QRG(2), except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.

Defined in [GW05], where it was also shown that SQG contains QIP.

SQG is contained in EXP [Gut05].

SQG is trivially contained in QRG(4) (and hence EXP).

SQG trivially contains QRG(2) (and hence PSPACE).

SQG is contained in PSPACE [GW10]. Hence SQG = QRG(2) = RG(2) = PSPACE and the addition of quantum information, combined with the ability of the verifier to process the one prover's answer before preparing the other prover's question, has no effect on the complexity of two-turn (one-round) zero-sum games.

More about...

UAP: Unambiguous Alternating Polynomial-Time

Same as AP, except we are promised that each existential quantifier has at most one 'yes' path, and each universal quantifier has at most one 'no' path.

Contains UP.

Defined in [NR98], where it was also shown that, even though AP = PSPACE, it is unlikely that the same is true for UAP, since UAP is contained in SPP.

[CGR+04] have also shown that UAP^UAP = UAP, and that UAP contains Graph Isomorphism problem.

More about...