Complexity Zoo:A

From Complexity Zoo
Revision as of 04:16, 25 October 2023 by ZTKing (talk | contribs) (→‎Ack: Ackermann Time)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

A0PP - AC - AC0 - AC0[m] - AC1 - ACC0 - Ack - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AMcc - AMEXP - 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

A0PP: 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:

  • A0PP contains QMA, AWPP, and coC=P.
  • A0PP is contained in PP.
  • If A0PP = PP then PH is contained in PP.

Kuperberg ([Kup09]) showed that A0PP = SBQP.

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

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

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

ACi is contained in NCi+1; thus, AC = NC.

AC1 contains NL.

For a random oracle A, (ACi)A is strictly contained in (ACi+1)A, and (uniform) ACA is strictly contained in PA, with probability 1 [Mil92].

FO-uniform AC with depth is equal to FO[].

AC0: 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 AC0 [FSS84].

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

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

Although there are no good pseudorandom functions in AC0, [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.

AC0 contains NC0, and is contained in QACf0 and MAC0.

In descriptive complexity, uniform AC0 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 AC0 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).

AC0[m]: AC0 With MOD m Gates

Same as AC0, 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 AC0[m] [Raz87] [Smo87]. It follows that, for any such m, AC0[m] is strictly contained in NC1.

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

See also: QAC0[m].

AC1: Unbounded Fanin Log-Depth Circuits

See AC for definition.

Contains NL (hence also NC1). Contained in NC2. The complexity class DET also obeys all these containment relationships, but no containment is known in either direction between AC1 and DET.

ACC0: AC0 With Arbitrary MOD Gates

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

Contained in TC0.

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

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

Contains 4-PBP [BT88].

See also: QACC0 and CC0.

Ack: Ackermann Time

Defined in [Sch16]. Let and where is applied to itself times. For example , , etc. Then define, , note that this has the same growth rate as where A is the Ackermann function. This class is equal to DTIME(Fω(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace DTIME with NTIME or DSPACE.

Strictly contains ELEMENTARY, Tower, and PR. Is strictly contained in R.

The relationship between this class and PR is analogous to the relationship between Tower and ELEMENTARY. That is, Ack contains problems "barely" outside of PR and, unlike PR, has complete problems.

The reachability problems for Petri nets [Ler22] and vector addition systems [CO22] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [Ani+23].

AH: Arithmetic Hierarchy

The analog of PH in computability theory.

Let Δ0 = Σ0 = Π0 = 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: is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and . A bounded quantifier is of the form or where is considered to be free in . Then is the sets of number validating a formula of the form with . The set Πi is the set of formula who are negation of 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 MAEXP/rpoly = ALL.

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

On the other hand, even though PSPACE contains PP, and EXPSPACE contains MAEXP, 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, MAEXP/rpoly means M(AEXP/rpoly), while (MAEXP)/rpoly equals MAEXP/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 UE*-uniform NC1.

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 NPA

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

Equals AM [NW94].

Almost-P: Languages Almost Surely in PA

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

Equals BPP [BG81].

Almost-PSPACE: Languages Almost Surely in PSPACEA

The class of problems that are in PSPACEA 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 = BPexpPSPACE, where BPexp is like the BP⋅ operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXPNPcoNEXPNP.

Whereas both BPexpPSPACE 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 Π2P and this proof relativizes so the containment holds relative to any oracle.

If AM contains coNP then PH collapses to Σ2PΠ2P [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 NEcoNE 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.)

AMcc: 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 AMcc.

Contained in PHcc.

AMcc ∩ coAMcc is not contained in PPcc if partial functions are allowed [Kla11].

AMEXP: Exponential-Time AM

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

Contains MAEXP, and is contained in EH and indeed S2-EXP•PNP.

If coNP is contained in AM[polylog] then EH collapses to AMEXP [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 S2-EXP•PNP. ([PV04] improved the collapse to AMEXP.)

AmpMP: Amplifiable MP

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

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


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(1n) > 1-2-p(n).
  2. If the answer is "no" then 0 < f(x)/g(1n) < 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 is the class of decision problems solvable with polynomial space by an alternating Turing machine. See also ASPACE.


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 space bounded by f(n). See also ATIME.

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

For any polynomial time constructable f(n) > n, ASPACE(log(f(n))) = DTIME(poly(f(n))). [CKS81].

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

For any polynomial time constructable f(n) > n, ATIME(poly(f(n))) = SPACE(poly(f(n))). [CKS81].

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 NAuxPDAp 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,k1,...,kr) (r,k1,...,kr 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 S1,...,Sr. Does there exist an assignment to S1 of Hamming weight k1, such that for all assignments to S2 of Hamming weight k2, 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}n 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}n 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].