Complexity Zoo:A

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

A₀PP - AC - AC⁰ - AC⁰[m] - AC¹ - ACC⁰ - Ack - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AM^cc - AM_EXP - AM ∩ coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - APP - APSPACE - APX - ASPACE - ATIME - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - AxP - AxPP

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.

Kuperberg ([Kup09]) showed that A₀PP = SBQP.

---

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

fo-uniform AC with depth $t(n)$ is equal to FO[$t(n)$]

---

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_f⁰ 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]). So it's equivalent to the class FO, and to the alternating logtime hierarchy.

[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 (e.g. 6), then it is not even known whether AC⁰[m] = NP!

See also: QAC⁰[m].

---

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

There is no non-uniform ACC⁰ circuits of polynomial size for NTIMES[2ⁿ] and no ACC⁰ circuit of size 2^nO(1) for E^NP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC⁰ and were recently discovered by [Wil11].

Contains 4-PBP [BT88].

See also: QACC⁰.

---

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.

An equivalent definition is: $\Sigma _{0}=\Delta _{0}=\Pi _{0}$ is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and $\times$. A bounded quantifier is of the form $\phi =\forall i<j\psi$ or $\phi =\exists i<j\psi$ where $j$ is considered to be free in $\phi$. Then $\Sigma _{i+1}$ is the sets of number validating a formula of the form $\exists X_{1}\dots \exists X_{n},\psi$ with $\psi \in \Delta _{i}$. The set Π_i is the set of formula who are negation of $\Sigma _{i}$ formula. And Δ_i = Σ_i ∩ Π_i.

---

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.

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.

---

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&#149;PSPACE, where BP^exp&#149; is like the BP&#149; operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXP^NP ∩ coNEXP^NP.

Whereas both BP^exp&#149;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

1. 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).
2. 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 NP/poly. AM is also contained in Π₂P and this proof relativizes so the containment holds relative to any oracle.

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^cc: Communication Complexity AM

Here, Alice and Bob collectively constitute "Arthur", and Merlin sends a message that depends on the input and all the randomness, and the cost is defined to be the bit length of Merlin's message plus the communication cost of the ensuing verification protocol between Alice and Bob. (Without loss of generality, the verification protocol consists only of checking containment in a rectangle, since Merlin could always include the transcript of the verification in his message.)

It is open to prove that there exists an explicit two-party function that is not in AM^cc.

Contained in PH^cc.

AM^cc ∩ coAM^cc is not contained in PP^cc if partial functions are allowed [Kla11].

---

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

1. The answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
2. 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|,

1. If the answer is "yes" then 1 > f(x)/g(1ⁿ) > 1-2^-p(n).
2. 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.

---

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

---

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

---

ASPACE: Alternating SPACE

ASPACE(f(n)) is the class of problems for which there are alternating Turing machines (see AP) which decide the problem in time bounded by f(n). See also ATIME.

In particular, APSPACE = ASPACE(poly(n)) and AL = ASPACE(log(n)).

---

ATIME: Alternating TIME

ATIME(f(n)) is the class of problems for which there are alternating Turing machines (see AP) which decide the problem in time bounded by f(n). See also ASPACE.

In particular, AP = ATIME(poly(n)) and ALOGTIME = ATIME(log(n)).

---

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

Strictly contained in HeurP [NS05].

See also: (NP,P-samplable).

---

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,

1. 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).
2. 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: 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].

---

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

[DFT98] show that for all t, AW[t] = 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.

AxPP is recursively enumerable [Jeř07].