Complexity Zoo 1.0

From Qwiki

Introduction

Welcome to the Complexity Zoo... There are now 468 classes and counting!

what's your problem?

This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators:

Zookeeper: Scott Aaronson
Veterinarian: Greg Kuperberg

Errors? Omissions? Misattributions? Your favorite class not here? Then please contribute to the zoo as you see fit by signing up and clicking on the edit links. Please include references, or better yet links to papers if available.

To create a new class, click on the edit link of the class before or after the one that you want to add and copy the format of that class. (The classes are alphabetized by their tag names.) Then add the class to the table of contents and increment the total number of classes. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our simple wiki help page.

If you would like to contribute but feel unable to make the updates yourself, email the zookeeper at scott at scottaaronson.com.

The Classes

Warning: Please do not feed oracles to the complexity classes! These classes require a specially balanced diet to ensure proper relativization.

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

1NAuxPDA^p: One-Way NAuxPDA^p

Defined in [Bra77], where it was also shown that 1NAuxPDA^p strictly contains CFL and is strictly contained in LOGCFL. The class corresponds to the closure of CFL under one-way log-space reductions.

#AC⁰: Sharp-AC⁰

The class of functions from {0,1}ⁿ to nonnegative integers computed by polynomial-size constant-depth arithmetic circuits, using addition and multiplication gates and the constants 0 and 1.

Contained in GapAC⁰.

#GA: Graph Automorphism

The class of problems (Karp-)reducible to counting the number of automorphisms of a graph.

Counterpart of GA.

#L: Sharp-L

Has the same relation to L as #P does to P.

#L is contained in DET [AJ93].

#L/poly: Nonuniform #L

Has the same relation to #L as P/poly does to P.

#P: Sharp-P

The class of function problems of the form "compute f(x)," where f is the number of accepting paths of an NP machine.

The canonical #P-complete problem is #SAT.

Defined in [Val79], where it was also shown that #Perfect Matching (or equivalently, Permanent) is #P-complete. What makes that interesting is that the associated decision problem Perfect Matching is in P.

PH is in P^#P [Tod89].

Any function in #P can be approximated to within a polynomial factor in BPP with NP oracle [Sto85].

#W[t]: Sharp-W[t]

Roughly, the analogue of #P for parameterized complexity. I.e. the class of parameterized counting problems that are fixed-parameter parsimonious reducible to #WSAT. Defined in [FG02], which should be consulted for the full definition. [FG02] also showed that there exist #W[1]-complete problems whose corresponding decision problems are fixed-parameter tractable (i.e. in FPT).

⊕EXP: Parity EXP

The exponential-time analogue of ⊕P.

There exists an oracle relative to which ⊕EXP = ZPP [BBF98].

⊕L: Parity L

Has the same relation to L as ⊕P does to P.

Contains SL [KW93].

Solving a linear system over Z₂ is complete for ⊕L [Dam90].

⊕L^⊕L = ⊕L [HRV00].

⊕L/poly: Nonuniform ⊕L

Has the same relation to ⊕L as P/poly does to P.

Contains NL/poly [GW96].

⊕P: Parity P

The class of decision problems solvable by an NP machine such that

If the answer is 'yes,' then the number of accepting paths is odd.
If the answer is 'no,' then the number of accepting paths is even.

Defined in [PZ83].

Contains Graph Isomorphism; indeed, Graph Isomorphism is low for ⊕P [AK02].

Contains FewP [CH89].

There exists an oracle relative to which P = ⊕P but P is not equal to NP (and indeed NP = EXP) [BBF98].

Equals Mod_2^mP for every positive integer m.

⊕SAC⁰: AC⁰ With Unbounded Parity Gates

⊕SAC¹: AC¹ With Unbounded Parity Gates

The class of problems solvable by a nonuniform family of polynomial-size, polylog-depth circuits with unbounded-fanin XOR and bounded-fanin AND gates.

Defined in [GW96], where it was also shown that ⊕SAC¹ contains SAC¹.

A₀PP: One-Sided Analog of AWPP

Same as SBP, except that f is a nonnegative-valued GapP function rather than a #P function.

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

A₀PP contains QMA, AWPP, and coC₌P.
A₀PP is contained in PP.
If A₀PP = PP then PH is contained in PP.

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

ACⁱ is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.

Then AC is the union of ACⁱ over all nonnegative i.

ACⁱ is contained in NCⁱ⁺¹; thus, AC = NC.

Contains NL.

For a random oracle A, (ACⁱ)^A is strictly contained in (ACⁱ⁺¹)^A, and (uniform) AC^A is strictly contained in P^A, with probability 1 [Mil92].

AC⁰: Unbounded Fanin Constant-Depth Circuits

An especially important subclass of AC, corresponding to constant-depth, unbounded-fanin, polynomial-size circuits with AND, OR, and NOT gates.

Computing the Parity or Majority of n bits is not in AC⁰ [FSS84].

There are functions in AC⁰ that are pseudorandom for all statistical tests in AC⁰ [NW94]. But there are no functions in AC⁰ that are pseudorandom for all statistical tests in QP (quasipolynomial time) [LMN93].

[LMN93] showed furthermore that functions with AC⁰ circuits of depth d are learnable in QP, given their outputs on O(2^{log(n)^O(d)}) randomly chosen inputs. On the other hand, this learning algorithm is essentially optimal, unless there is a 2^{n^o(1)} algorithm for factoring [Kha93].

Although there are no good pseudorandom functions in AC⁰, [IN96] showed that there are pseudorandom generators that stretch n bits to n+Θ(log n), assuming the hardness of a problem based on subset sum.

AC⁰ contains NC⁰, and is contained in QAC⁰ and MAC⁰.

In descriptive complexity, uniform AC⁰ can be characterized as the class of problems expressible by first-order predicates with addition and multiplication operators - or indeed, with ordering and multiplication, or ordering and division (see [Lee02]).

[BLM+98] showed the following problem is complete for depth-k AC⁰ circuits (with a uniformity condition):

Given a grid graph of polynomial length and width k, decide whether there is a path between vertices s and t (which can be given as part of the input).

AC⁰[m]: AC⁰ With MOD m Gates

Same as AC⁰, but now "MOD m" gates (for a specific m) are allowed in addition to AND, OR, and NOT gates. (A MOD m gate outputs 0 if the sum of its inputs is congruent to 0 modulo m, and 1 otherwise.)

If m is a power of a prime p, then for any prime q not equal to p, deciding whether the sum of n bits is congruent to 0 modulo q is not in AC⁰[m] [Raz87] [Smo87]. It follows that, for any such m, AC⁰[m] is strictly contained in NC¹.

However, if m is a product of distinct primes (i.e. 6), then it is not even known whether AC⁰[m] = NP!

AC¹: Unbounded Fanin Log-Depth Circuits

See AC.

ACC⁰: AC⁰ With Arbitrary MOD Gates

Same as AC⁰[m], but now the constant-depth circuit can contain MOD m gates for any m.

Contained in TC⁰.

Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].

According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC⁰. On the other hand, no nontrivial lower bounds against ACC⁰ are known either. Thus, this class represents the current frontier for circuit lower bounds.

Contains 4-PBP [BT88].

AH: Arithmetic Hierarchy

The analog of PH in computability theory.

Let Δ₀ = Σ₀ = Π₀ = R. Then for i>0, let

Δ_i = R with Σ_i-1 oracle.
Σ_i = RE with Σ_i-1 oracle.
Π_i = coRE with Σ_i-1 oracle.

Then AH is the union of these classes for all nonnegative constant i.

Each level of AH strictly contains the levels below it.

AL: Alternating L

Same as AP, but for logarithmic-space instead of polynomial-time.

AL = P [CKS81].

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.

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.

ALOGTIME: Logarithmic time alternating RAM

ALOGTIME is the class of languages decidable in logarithmic time by a random access alternating Turing machine.

Known to be equal to U_E^*-uniform NC¹.

AlgP/poly: Polynomial-Size Algebraic Circuits

The class of multivariate polynomials over the integers that can be evaluated using a polynomial (in the input size n) number of additions, subtractions, and multiplications, together with the constants -1 and 1. The class is nonuniform, in the sense that the polynomial for each input size n can be completely different.

Named in [Imp02], though it has been considered since the 1970's.

If P = BPP (or even BPP is contained in NE), then either NEXP is not in P/poly, or else the permanent polynomial of a matrix is not in AlgP/poly [KI02].

Almost-NP: Languages Almost Surely in NP^A

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

Equals AM [NW94].

Almost-P: Languages Almost Surely in P^A

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

Equals BPP [BG81].

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.

AM: Arthur-Merlin

The class of decision problems for which a "yes" answer can be verified by an Arthur-Merlin protocol, as follows.

Arthur, a BPP (i.e. probabilistic polynomial-time) verifier, generates a "challenge" based on the input, and sends it together with his random coins to Merlin. Merlin sends back a response, and then Arthur decides whether to accept. Given an algorithm for Arthur, we require that

If the answer is "yes," then Merlin can act in such a way that Arthur accepts with probability at least 2/3 (over the choice of Arthur's random bits).
If the answer is "no," then however Merlin acts, Arthur will reject with probability at least 2/3.

Surprisingly, it turns out that such a system is just as powerful as a private-coin one, in which Arthur does not need to send his random coins to Merlin [GS86]. So, Arthur never needs to hide information from Merlin.

Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have k rounds of interaction. Then for all constant k>2, AM[k] = AM[2] = AM [BM88]. Also, the result of [GS86] can then be stated as follows: IP[k] is contained in AM[k+2] for every k (constant or non-constant).

AM contains graph nonisomorphism.

Contains NP, BPP, and SZK, and is contained in Π₂P and NP/poly.

If AM contains coNP then PH collapses to Σ₂P ∩ Π₂P [BHZ87].

There exists an oracle relative to which AM is not contained in PP [Ver92].

AM = NP under a strong derandomization assumption: namely that some language in NE ∩ coNE requires nondeterministic circuits of size 2^Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)

AM_EXP: Exponential-Time AM

Same as AM, except that Arthur is exponential-time and can exchange exponentially long messages with Merlin.

Contains MA_EXP, and is contained in EH and indeed S₂-EXP•P^NP.

If coNP is contained in AM[polylog] then EH collapses to AM_EXP [PV04].

AM ∩ coAM

The class of decision problems for which both "yes" and "no" answers can be verified by an AM protocol.

If EXP requires exponential time even for AM protocols, then AM ∩ coAM = NP ∩ coNP [GST03].

There exists an oracle relative to which AM ∩ coAM is not contained in PP [Ver95].

AM[polylog]: AM With Polylog Rounds

Same as AM, except that we allow polylog(n) rounds of interaction between Arthur and Merlin instead of a constant number.

Not much is known about AM[polylog] -- for example, whether it sits in PH. However, [SS04] show that if AM[polylog] contains coNP, then EH collapses to S₂-EXP•P^NP. ([PV04] improved the collapse to AM_EXP.)

AmpMP: Amplifiable MP

The class of decision problems such that for some #P function f(x,0^m),

The answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
The m bits of f(x) to the left and right of the middle bit are all 0.

Defined in [GKR+95].

Contains PH and Contained in MP.

AmpP-BQP: BQP Restricted To AmpP States

Similar to TreeBQP except that the quantum computer's state at each time step is restricted to being exponentially close to a state in AmpP (that is, a state for which the amplitudes are computable by a classical polynomial-size circuit).

Defined in [Aar03b], where it was also observed that AmpP-BQP is contained in the third level of PH, just as TreeBQP is.

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.

APP: Amplified PP

Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist GapP functions f and g such that for all inputs x with n=|x|,

If the answer is "yes" then 1 > f(x)/g(1ⁿ) > 1-2^-p(n).
If the answer is "no" then 0 < f(x)/g(1ⁿ) < 2^-p(n).

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

APP is contained in PP, and indeed is low for PP.
APP is closed under intersection, union, and complement.

APP contains AWPP [Fen02].

The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.

APX: Approximable

The subclass of NPO problems that admit constant-factor approximation algorithms. (I.e., there is a polynomial-time algorithm that is guaranteed to find a solution within a constant factor of the optimum cost.)

Contains PTAS.

Equals the closure of MaxSNP and of MaxNP under PTAS reduction [KMS+99], [CT94].

Defined in [ACG+99].

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.

AuxPDA: Auxiliary Pushdown Automata

Equivalent to NAuxPDA^p without the running-time restriction.

Equals P [Coo71b].

AVBPP: Average-Case BPP

Defined in [OW93] to be the class of decision problems that have a good average-case BPP algorithm, whenever the input is chosen from an efficiently samplable distribution.

Note that this is not the same as the BPP version of AvgP.

AvgE: Average Exponential-Time With Linear Exponent

Has the same relation to E as AvgP does to P.

AvgP: Average Polynomial-Time

A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.

A function f, from strings to integers, is polynomial on μ-average if there exists a constant ε>0 such that the expectation of f^ε(x) is finite, when x is drawn from μ.

Then (A,μ) is in AvgP if there is an algorithm for A whose running time is polynomial on μ-average.

This convoluted definition is due to Levin [Lev86], who realized that simpler definitions lead to classes that fail to satisfy basic closure properties. Also see [Gol97] for more information.

If AvgP = DistNP then EXP = NEXP [BCG+92].

AW[P]: Alternating W[P]

Same as AW[SAT] but with 'circuit' instead of 'formula.'

Has the same relation to AW[SAT] as W[P] has to W[SAT].

Defined in [DF99].

AWPP: Almost WPP

The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,

If the answer is "no," then the difference between the number of accepting and rejecting paths is non-negative and at most 2^-poly(n)f(x).
If the answer is "yes," then the difference is between (1-2^-poly(n))f(x) and f(x).

Defined in [FFK94].

Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.

Contained in APP [Fen02].

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:

₁

₂

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

Defined in [DF99].

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

AW[]: Alternating W[]

The union of AW[t] over all t.

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

AxP: Approximable in Polynomial Time

Usually called AP in the literature. I've renamed it AxP to distinguish it from the "other" AP.

The class of real-valued functions from {0,1}ⁿ to [0,1] that can be approximated within any ε>0 by a deterministic Turing machine in time polynomial in n and 1/ε.

Defined by [KRC00], who also showed that the set of AxP machines is in RE.

AxPP: Approximable in Probabilistic Polynomial Time

Usually called APP. I've renamed it AxPP to distinguish it from the "other" APP.

The class of real-valued functions from {0,1}ⁿ to [0,1] that can be approximated within any ε>0 by a probabilistic Turing machine in time polynomial in n and 1/ε.

Defined by [KRC00], who also show the following:

Approximating the acceptance probability of a Boolean circuit is AxPP-complete. The authors argue that this makes AxPP a more natural class than BPP, since the latter is not believed to have complete problems.
If AxPP = AxP, then BPP = P.
On the other hand, there exists an oracle relative to which BPP = P but AxPP does not equal AxP.

Interestingly, it is unclear whether the set of AxPP machines is in RE.

βP: Limited-Nondeterminism NP

β_kP is the class of decision problems solvable by a polynomial-time Turing machine that makes O(log^kn) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(log^kn) that the answer is 'yes.'

Then βP is the union of β_kP over all constant k.

Defined in [KF84]. See also the survey [GLM96].

There exist oracles relative to which basically any consistent inclusion structure among the β_kP's can be realized [BG98].

β₂P contains LOGNP and LOGSNP.

BH: Boolean Hierarchy Over NP

The smallest class that contains NP and is closed under union, intersection, and complement.

The levels are defined as follows:

BH₁ = NP.
BH_2i is the class of languages that are the intersection of a BH_2i-1 language with a coNP language.
BH_2i+1 is the class of languages that are the union of a BH_2i language with an NP language.

Then BH is the union over all i of BH_i.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ₂P and indeed in P^NP[log].

If BH collapses at any level, then PH collapses to Σ₃P [Kad88].

BP_d(P): Polynomial Size d-Times-Only Branching Program

Defined in [Weg88].

The class of decision problems solvable by a family of polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times.

BP_d(P) strictly contains BP_d-1(P), for every d > 1 [Tha98].

Contained in PBP.

BPE: Bounded-Error Probabilistic E

Has the same relation to E as BPP does to P.

EE = BPE if and only if EXP = BPP [IKW01].

BPEE: Bounded-Error Probabilistic EE

Has the same relation to EE as BPP does to P.

BP_HSPACE(f(n)): Bounded-Error Halting Probabilistic f(n)-Space

The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts on every input and every random tape setting.

Contains R_HSPACE(f(n)).

Is contained in DSPACE(f(n)^3/2) [SZ95].

BPL: Bounded-Error Probabilistic L

Has the same relation to L as BPP does to P. The Turing machine has to halt with probability 1 on every input.

Contained in SC [Nis92] and in PL.

BP•NP: Probabilistic NP

Equals AM.

BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

If the answer is 'yes' then at least 2/3 of the computation paths accept.
If the answer is 'no' then at most 1/3 of the computation paths accept.

(Here all computation paths have the same length.)

Often identified as the class of feasible problems for a computer with access to a genuine random-number source.

Defined in [Gil77].

Contained in Σ₂P ∩ Π₂P [Lau83], and indeed in ZPP^NP [GZ97].

If BPP contains NP, then RP = NP [Ko82] and PH is contained in BPP [Zac88].

If any problem in E requires circuits of size 2^Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).

Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].

BPP is not known to contain complete problems. [Sip82], [HH86] give oracles relative to which BPP has no complete problems.

There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].

In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(n^c) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.

Equals Almost-P.

BPP^cc: Communication Complexity BPP

The analogue of P^cc for bounded-error probabilistic communication complexity.

Does not equal P^cc, and is not contained in NP^cc, because of the EQUALITY problem.

Defined in [BFS86].

BPP^KT: BPP With Time-Bounded Kolmogorov Complexity Oracle

BPP with an oracle that, given a string x, returns the minimum over all programs P that output x_i on input i, of the length of P plus the maximum time taken by P on any input.

A similar class was defined in [ABK+02], where it was also shown that in BPP^KT one can factor, compute discrete logarithms, and more generally invert any one-way function on a non-negligible fraction of inputs.

BPP/log: BPP With Logarithmic Karp-Lipton Advice

The class of problems solvable by a semantic BPP machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, the machine must provide some answer with probability at least 2/3. See the discussion for BQP/poly.

Contained in BPP/mlog.

BPP/mlog: BPP With Logarithmic Deterministic Merlin-Like Advice

The class of problems solvable by a syntactic BPP machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, it need not be.

Contained in BPP/rlog.

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 then EXP = BPP, and if PSPACE is in BPP//log then PSPACE = BPP.

BPP/rlog: BPP With Logarithmic Deterministic Merlin-Like Advice

The class of problems solvable by a syntactic BPP machine with O(log n) random advice bits whose probability distribution depends only on the input length n. For each n, there exists good advice such that the output is correct with probability at least 2/3.

Contains BPP/mlog. The inclusion is strict, because BPP/rlog contains any finitely sparse language by fingerprinting; see the discussion for ALL.

Contained in BPP//log.

BPP-OBDD: Polynomial-Size Bounded-Error Ordered Binary Decision Diagram

Same as P-OBDD, except that probabilistic transitions are allowed and the OBDD need only accept with probability at least 2/3.

Does not contain the integer multiplication problem [AK96].

Strictly contained in BQP-OBDD [NHK00].

BPP_path: Threshold BPP

Same as BPP, except that now the computation paths need not all have the same length.

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

BPP_path contains MA and P^NP[log], and is contained in PP and BPP^NP.
BPP_path is closed under complementation, intersection, and union.
If BPP_path = BPP_path^BPPpath, then PH collapses to BPP_path.
If BPP_path contains Σ₂P, then PH collapses to BPP^NP.

There exists an oracle relative to which BPP_path is not contained in Σ₂P [BGM02].

BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2^{O((log n)^k)}); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.

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

EXP

BPTIME

^{(log n)^a}

BPTIME

^{(log n)^b}

BPSPACE(f(n)): Bounded-Error Probabilistic f(n)-Space

The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts with probability 1 on every input.

Contains RSPACE(f(n)) and BP_HSPACE(f(n)).

BPTIME(f(n)): Bounded-Error Probabilistic f(n)-Time

Same as BPP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [Gil77].

BPTIME(n^{log n}) does not equal BPTIME(2^{n^ε}) for any ε>0 [KV88]. Proving a stronger time hierarchy theorem for BPTIME is a longstanding open problem; see [BH97] for details.

[Bar02] has shown the following:

If we allow a small number of advice bits (say log n), then there is a strict hierarchy: for every d at least 1, BPTIME(n^d)/(log n) does not equal BPTIME(n^d+1)/(log n).
In the uniform setting, if BPP has complete problems then BPTIME(n^d) does not equal BPTIME(n^d+1).
BPTIME(n) does not equal NP.

Subsequently, [FS04] managed to reduce the number of advice bits to only 1: BPTIME(n^d)/1 does not equal BPTIME(n^d+1)/1. They also proved a hierarchy theorem for HeurBPTIME.

For another bounded-error hierarchy result, see BPQP.

BQNC: Alternate Name for QNC

BQNP: Alternate Name for QMA

BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQP^BQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

BQP does not equal BPP [BV97] (and by similar arguments, is not in P/poly).
BQP is not contained in MA [Wat00].
BQP is not contained in Mod_pP for prime p [GV02].
NP, and indeed NP ∩ coNP, are not contained in BQP (in fact, this holds with probability 1 relative to a random oracle and a random permutation oracle, respectively) [BBB+97].
SZK is not contained in BQP [Aar02].
BQP is not contained in SZK (follows easily using the quantum walk problem in [CCD+03]).

BQP/log: BQP With Logarithmic-Size Karp-Lipton Advice

Same as BQP/poly except that the advice is O(log n) bits instead of a polynomial number.

Contained in BQP/mlog.

BQP/poly: BQP With Polynomial-Size Karp-Lipton Advice

Is to BQP/mpoly as ∃BPP is to MA. Namely, the BQP machine is required to give some answer with probability at least 2/3 even if the advice is bad. Even though BQP/mpoly is a more natural class, BQP/poly follows the standard definition of advice as a class operator [KL82].

Contained in BQP/mpoly and contains BQP/log.

BQP/mlog: BQP With Logarithmic-Size Deterministic Merlin-Like Advice

Same as BQP/mpoly except that the advice is O(log n) bits instead of a polynomial number.

Strictly contained in BQP/qlog [NY03].

BQP/mpoly: BQP With Polynomial-Size Deterministic Merlin-Like Advice

The class of languages recognized by a syntactic BQP machine with deterministic polynomial advice that depends only on the input length, such that the output is correct with probability 2/3 when the advice is good.

Can also be defined as the class of problems solvable by a nonuniform family of polynomial-size quantum circuits, just as P/poly is the class solvable by a nonuniform family of polynomial-size classical circuits.

Referred to with a variety of other ad hoc names, including BQP/poly on occassion.

Contains BQP/qlog, and is contained in BQP/qpoly.

Does not contain ESPACE [NY03].

BQP/qlog: BQP With Logarithmic-Size Quantum Advice

Same as BQP/mlog except that the advice is quantum instead of classical.

Strictly contains BQP/mlog [NY03].

Contained in BQP/mpoly.

BQP/qpoly: BQP With Polynomial-Size Quantum Advice

The class of problems solvable by a BQP machine that receives a quantum state ψ_n as advice, which depends only on the input length n.

As with BQP/mpoly, the acceptance probability does not need to be bounded away from 1/2 if the machine is given bad advice. (Thus, we are discussing the class that [NY03] call BQP/*Qpoly.) Indeed, such a condition would make quantum advice unusable, by a continuity argument.

Does not contain EESPACE [NY03].

[Aar04b] shows the following:

There exists an oracle relative to which BQP/qpoly does not contain NP.
BQP/qpoly is contained in PP/poly.

A classical oracle separation between BQP/qpoly and BQP/mpoly is presently unknown, but there is a quantum oracle separation [AK06]. An unrelativized separation is too much to hope for, since it would imply that PP is not contained in P/poly.

Contains BQP/mpoly.

BQP-OBDD: Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram

Same as P-OBDD, except that unitary (quantum) transitions are allowed and the OBDD need only accept with probability at least 2/3.

Strictly contains BPP-OBDD [NHK00].

BQPSPACE: Bounded-Error Quantum PSPACE

Equals PSPACE and PPSPACE.

BQTIME(f(n)): Bounded-Error Quantum f(n)-Time

Same as BQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [BV97].

BQP_tt/poly: BQP/mpoly With Truth-Table Queries

Same as BQP/mpoly, except that the machine only gets to make nonadaptive queries to whatever oracle it might have.

Defined in [NY03b], where it was also shown that P is not contained in BQP_tt/poly relative to an oracle.

k-BWBP: Bounded-Width Branching Program

Alternate name for k-PBP.

C₌AC⁰: Exact-Counting AC⁰

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 PAC⁰ under logspace uniformity [ABL98].

C₌L: Exact-Counting L

Has the same relation to L as C₌P does to P.

C₌L^C=L = L^C=L [ABO99].

C₌P: Exact-Counting Polynomial-Time

The class of decision problems solvable by an NP machine such that the number of accepting paths exactly equals the number of rejecting paths, if and only if the answer is 'yes.'

Equals coNQP [FGH+98].

CFL: Context-Free Languages

Does not equal QCFL [MC00].

Contained in LOGCFL.

Strictly contains DCFL [Bra77].

CH: Counting Hierarchy

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

Contained in PSPACE.

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

Check: Checkable Languages

The class of problems such that a polynomial-time program P that allegedly solves them can be checked efficiently. That is, f is in Check if there exists a BPP algorithm C such that for all programs P and inputs x,

If P(y)=f(y) for all inputs y, then C^P(x) (C with oracle access to P) accepts with probability at least 2/3.
If P(x) is not equal to f(x) then C^P(x) accepts with probability at most 1/3.

Introduced in [BK89], where it was also shown that Check equals frIP ∩ cofrIP.

Check is contained in NEXP ∩ coNEXP [FRS88].

[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.

CL#P: Cluster Sharp-P

The class of #P function problems such that some underlying NP machine $M$ witnessing membership in #P has "clustered" accepting paths. That is:

There exists a polynomial $p$ such that each computation path of $M$ on each input $x$ is exactly $p ( | x | )$ bits long.
There is a length-respecting total order $A$ having polynomial-time computable adjacency checks on the computation paths of $M$ .
The accepting paths of $M$ on any input $x$ are contiguous with respect to $A$ .

Defined in [HHK+05].

C_kP: k^th Level of CH

Defined as follows:

C₀P = P
C₁P = PP
C₂P = PP^PP
In general, C_k+1P is PP with C_kP oracle

The union of the C_kP's is called the counting hierarchy, CH.

Defined in [Wag86].

See [Tor91] or [AW90] for more information.

CLOG: Continuous Logarithmic-Time

Roughly, the class of continuous problems solvable by an ordinary differential equation (ODE) with convergence time logarithmic in the size of the input. The vector field of the ODE is specified by an NC¹ formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.

Defined in [BSF02], which should be consulted for more details.

[BSF02] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of NC¹, not of DTIME(log n).

Contained in CP.

CNP: Continuous NP

A nondeterministic analog of CP. Defined in [SF98], which should be consulted for the definition (it has something to do with strange attractors, I think).

The authors raise the question of whether CP equals CNP.

coAM: Complement of AM

coC₌P: Complement of C₌P

Equals NQP [FGH+98].

cofrIP: Complement of frIP

Coh: Coherent Languages

The class of problems L that are efficiently autoreducible, in the sense that given an input x and access to an oracle for L, a BPP machine can compute L(x) by querying L only on points that differ from x.

Defined in [Yao90b].

[BG94] show that, assuming NEE is not contained in BPEE, Coh ∩ NP is not contained in any of compNP, Check, or frIP.

coMA: Complement of MA

coMod_kP: Complement of Mod_kP

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

compNP: Competitive NP Proof System

The class of decision problems L in NP such that, if the answer is "yes," then a proof can be constructed in polynomial time given access only to an oracle for L.

Contains NPC.

[BG94] show that compNP is contained in frIP, and that assuming NEE is not contained in BPEE, compNP does not equal NP.

coNE: Complement of NE

coNEXP: Complement of NEXP

Contained in NEXP/poly (folklore result reported in [weblog]).

coNL: Complement of NL

Equals NL [Imm88] [Sze87].

coNP: Complement of NP

If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.

If NP does not equal coNP, then P does not equal NP. But the other direction is not known.

coNP^cc: Complement of NP^cc

coNP/poly: Complement of NP/poly

If NP is contained in coNP/poly then PH collapses to S₂P^NP [CCH+01].

NP^{NP^NP^(coNP/poly ∩ NP)} = NP^{NP^NP} [HNO+96]

Note: At the suggestion of Luis Antuñes, the above specimen of the Complexity Zoo has been locked in a cage.

coNQP: Complement of NQP

Equals C₌P [FGH+98].

coRE: Complement of RE

Does not equal RE.

The problem "given a computable predicate P, is P true of all positive integers?" is coRE-complete.

coRNC: Complement of RNC

Contains the problem of whether a bipartite graph has a perfect matching [Kar86].

coRP: Complement of RP

Defined in [Gil77].

Contains the problem of testing whether an integer is prime [SS77].

coSL: Complement of SL

coSPARSE: Complement of SPARSE

coUCC: Complement of UCC

[Tor00] showed the following problem complete for coUCC under L reductions:

Given a colored graph G with at most two vertices having any given color, does G have any nontrivial automorphisms?

coUP: Complement of UP

CP: Continuous P

Same as CLOG, except that the convergence time can be polynomial rather than logarithmic in the input size.

Defined in [BSF02] and [SF98].

Finding a maximum flow, which is P-complete, can be done in CP [BSF02]. Based on this the authors argue that "P is contained in CP," but this seems hard to formalize, since CP is not a complexity class in the usual sense. They also conjecture that "CP is contained in P" (i.e. the class of ODE's they consider can be integrated efficiently on a standard Turing machine), but this is open.

Contained in CNP.

CSIZE(f(n)): Circuit Size f(n)

The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)).

So for example, CSIZE(poly(n)) (the union of CSIZE(n^k) over all k) equals P/poly.

Defined in [SM02] among other places.

CSL: Context Sensitive Languages

The class of languages generated by context-sensitive grammars.

Equals NSPACE(n) [Kur64].

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 Arthur's view of his interaction with Merlin, conditioned on Arthur's random coins, and (2) the distribution over views that Arthur can simulate without Merlin'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 his coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions.)

Assuming the existence of one-way functions, CZK contains NP [GMW91], and indeed 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.

D#P: Alternate Name for P^#P

DCFL: Deterministic CFL

The class of languages accepted by deterministic pushdown automata.

Defined in [GG66], where it was also shown that DCFL is strictly contained in CFL and strictly contains REG.

Δ₂P: P With NP Oracle

A level of PH, the polynomial hierarchy.

Contains BH.

There exists an oracle relative to which Δ₂P is not contained in PP [Bei94].

There exists another oracle relative to which Δ₂P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].

If P = NP, then any polynomial-size circuit C can be learned in Δ₂P with C oracle [Aar06].

δ-BPP: δ-Semi-Random BPP

Same as BPP, except that the random bit source is biased as follows. Each bit could depend on all the previous bits in arbitrarily complicated ways; the only promise is that the bit is 1 with probability in the range [δ,1-δ], conditioned on all previous bits.

So clearly 0-BPP = P and 1/2-BPP = BPP.

It turns out that, for any δ>0, δ-BPP = BPP [VV85], [Zuc91].

δ-RP: δ-Semi-Random RP

Same as δ-BPP, but for RP instead of BPP.

For any δ>0, δ-RP = RP [VV85].

DET: Determinant

The class of decision problems reducible in L to the problem of computing the determinant of an n-by-n matrix of n-bit integers.

Defined in [Coo85].

Contained in NC², and contains NL and PL [BCP83].

Graph isomorphism is hard for DET under L-reductions [Tor00].

DiffAC⁰: Difference #AC⁰

The class of functions from {0,1}ⁿ to integers expressible as the difference of two #AC⁰ functions.

Equals GapAC⁰ under logspace uniformity [ABL98].

DisNP: Disjoint NP Pairs

The class of pairs (A,B), where A and B are NP problems whose sets of "yes" instances are nonempty and disjoint.

If there exists an optimal propositional proof system, then DisNP has a complete pair [Raz94]. On the other hand, there exists an oracle relative to which DisNP does not have a complete pair [GSS+03].

If P does not equal UP, then DisNP contains pairs not separated by any set in P [GS88]. On the other hand, there exists an oracle relative to which P does not equal NP but still DisNP does not contain any P-inseparable pairs [HS92].

DistNP: Distributional NP

(also called (NP,P-computable) or RNP)

A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.

(A,μ) is in DistNP if A is in NP, and μ is P-computable (meaning that its cumulative density function can be evaluated in polynomial time).

DistNP has complete problems [Lev86] (see also [Gur87]), although unlike for NP this is not immediate.

Any DistNP-complete problem is also complete for (NP,P-samplable) [IL90].

DP: Difference Polynomial-Time

DP = BH₂, the second level of the Boolean hierarchy.

Defined in [PY84].

DQP: Dynamical Quantum Polynomial-Time

The class of decision problems solvable by a BQP machine with oracle access to a dynamical simulator. When given a polynomial-size quantum circuit, the simulator returns a sample from the distribution over "classical histories" induced by the circuit. The simulator can adversarially choose any history distribution that satisfies the axioms of "symmetry" and "locality" -- so that the DQP algorithm has to work for any distribution satisfying these axioms.

See [Aar05] for a full definition.

There it is also shown that SZK is contained in DQP.

Contains BQP, and is contained in EXP [Aar05].

There exists an oracle relative to which DQP does not contain NP [Aar05].

DSPACE(f(n)): Deterministic f(n)-Space

The class of decision problems solvable by a Turing machine in space O(f(n)).

The Space Hierarchy Theorem: For constructible f(n) greater than log n, DSPACE(f(n)) is strictly contained in DSPACE(f(n) log(f(n))) [HLS65].

For space constructible f(n), strictly contains DTIME(f(n))

Complexity Zoo 1.0

From Qwiki

Introduction

See Also

Table of Contents

The Classes

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

1NAuxPDAp: One-Way NAuxPDAp

#AC0: Sharp-AC0

#GA: Graph Automorphism

#L: Sharp-L

#L/poly: Nonuniform #L

#P: Sharp-P

#W[t]: Sharp-W[t]

⊕EXP: Parity EXP

⊕L: Parity L

⊕L/poly: Nonuniform ⊕L

⊕P: Parity P

⊕SAC0: AC0 With Unbounded Parity Gates

⊕SAC1: AC1 With Unbounded Parity Gates

A0PP: One-Sided Analog of AWPP

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

AC0: Unbounded Fanin Constant-Depth Circuits

AC0[m]: AC0 With MOD m Gates

AC1: Unbounded Fanin Log-Depth Circuits

ACC0: AC0 With Arbitrary MOD Gates

AH: Arithmetic Hierarchy

AL: Alternating L

ALL: The Class of All Languages

ALOGTIME: Logarithmic time alternating RAM

AlgP/poly: Polynomial-Size Algebraic Circuits

Almost-NP: Languages Almost Surely in NPA

Almost-P: Languages Almost Surely in PA

Almost-PSPACE: Languages Almost Surely in PSPACEA

AM: Arthur-Merlin

AMEXP: Exponential-Time AM

AM ∩ coAM

AM[polylog]: AM With Polylog Rounds

AmpMP: Amplifiable MP

AmpP-BQP: BQP Restricted To AmpP States

AP: Alternating P

APP: Amplified PP

APX: Approximable

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

AuxPDA: Auxiliary Pushdown Automata

AVBPP: Average-Case BPP

AvgE: Average Exponential-Time With Linear Exponent

AvgP: Average Polynomial-Time

AW[P]: Alternating W[P]

AWPP: Almost WPP

AW[SAT]: Alternating W[SAT]

AW[*]: Alternating W[*]

AW[t]: Alternating W[t]

AxP: Approximable in Polynomial Time

AxPP: Approximable in Probabilistic Polynomial Time

βP: Limited-Nondeterminism NP

BH: Boolean Hierarchy Over NP

BPd(P): Polynomial Size d-Times-Only Branching Program

BPE: Bounded-Error Probabilistic E

BPEE: Bounded-Error Probabilistic EE

BPHSPACE(f(n)): Bounded-Error Halting Probabilistic f(n)-Space

BPL: Bounded-Error Probabilistic L

BP•NP: Probabilistic NP

BPP: Bounded-Error Probabilistic Polynomial-Time

BPPcc: Communication Complexity BPP

BPPKT: BPP With Time-Bounded Kolmogorov Complexity Oracle

BPP/log: BPP With Logarithmic Karp-Lipton Advice

BPP/mlog: BPP With Logarithmic Deterministic Merlin-Like Advice

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

BPP/rlog: BPP With Logarithmic Deterministic Merlin-Like Advice

BPP-OBDD: Polynomial-Size Bounded-Error Ordered Binary Decision Diagram

BPPpath: Threshold BPP

BPQP: Bounded-Error Probabilistic QP

BPSPACE(f(n)): Bounded-Error Probabilistic f(n)-Space

BPTIME(f(n)): Bounded-Error Probabilistic f(n)-Time

BQNC: Alternate Name for QNC

BQNP: Alternate Name for QMA

BQP: Bounded-Error Quantum Polynomial-Time

BQP/log: BQP With Logarithmic-Size Karp-Lipton Advice

BQP/poly: BQP With Polynomial-Size Karp-Lipton Advice

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

1NAuxPDA^p: One-Way NAuxPDA^p

#AC⁰: Sharp-AC⁰

⊕SAC⁰: AC⁰ With Unbounded Parity Gates

⊕SAC¹: AC¹ With Unbounded Parity Gates

A₀PP: One-Sided Analog of AWPP

AC⁰: Unbounded Fanin Constant-Depth Circuits

AC⁰[m]: AC⁰ With MOD m Gates

AC¹: Unbounded Fanin Log-Depth Circuits

ACC⁰: AC⁰ With Arbitrary MOD Gates

Almost-NP: Languages Almost Surely in NP^A

Almost-P: Languages Almost Surely in P^A

Almost-PSPACE: Languages Almost Surely in PSPACE^A

AM_EXP: Exponential-Time AM

AW[]: Alternating W[]

BP_d(P): Polynomial Size d-Times-Only Branching Program

BP_HSPACE(f(n)): Bounded-Error Halting Probabilistic f(n)-Space

BPP^cc: Communication Complexity BPP

BPP^KT: BPP With Time-Bounded Kolmogorov Complexity Oracle

BPP_path: Threshold BPP

BQP_tt/poly: BQP/mpoly With Truth-Table Queries

C₌AC⁰: Exact-Counting AC⁰

C₌L: Exact-Counting L

C₌P: Exact-Counting Polynomial-Time

C_kP: k^th Level of CH

coC₌P: Complement of C₌P

coMod_kP: Complement of Mod_kP

coNP^cc: Complement of NP^cc

D#P: Alternate Name for P^#P

Δ₂P: P With NP Oracle

DiffAC⁰: Difference #AC⁰