# Difference between revisions of "Complexity Zoo:A"

Emil Jeřábek (talk | contribs) (→AC0: Unbounded Fanin Constant-Depth Circuits: Restore a deleted correct claim. (Only the reference to AL was wrong.)) |
|||

Line 179: | Line 179: | ||

AM contains [[Complexity_Garden#graph_isomorphism|graph nonisomorphism]]. | AM contains [[Complexity_Garden#graph_isomorphism|graph nonisomorphism]]. | ||

− | Contains [[Complexity Zoo:N#np|NP]], [[Complexity Zoo:B#bpp|BPP]], and [[Complexity Zoo:S#szk|SZK]], and is contained in [[Complexity Zoo:P#pi2p|Π<sub>2</sub>P]] and | + | Contains [[Complexity Zoo:N#np|NP]], [[Complexity Zoo:B#bpp|BPP]], and [[Complexity Zoo:S#szk|SZK]], and is contained in [[Complexity Zoo:N#nppoly|NP/poly]]. |

+ | AM is also contained in [[Complexity Zoo:P#pi2p|Π<sub>2</sub>P]] and this proof relativizes so the containment holds relative to any oracle. | ||

If AM contains [[Complexity Zoo:C#conp|coNP]] then [[Complexity Zoo:P#ph|PH]] collapses to [[Complexity Zoo:S#sigma2p|Σ<sub>2</sub>P]] ∩ [[Complexity Zoo:P#pi2p|Π<sub>2</sub>P]] [[zooref#bhz87|[BHZ87]]]. | If AM contains [[Complexity Zoo:C#conp|coNP]] then [[Complexity Zoo:P#ph|PH]] collapses to [[Complexity Zoo:S#sigma2p|Σ<sub>2</sub>P]] ∩ [[Complexity Zoo:P#pi2p|Π<sub>2</sub>P]] [[zooref#bhz87|[BHZ87]]]. | ||

Line 188: | Line 189: | ||

---- | ---- | ||

+ | |||

===== <span id="amcc" style="color:red">AM<sup>cc</sup></span>: Communication Complexity [[#am|AM]] ===== | ===== <span id="amcc" style="color:red">AM<sup>cc</sup></span>: Communication Complexity [[#am|AM]] ===== | ||

## Revision as of 13:20, 17 June 2020

*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_{0}PP -
AC -
AC^{0} -
AC^{0}[m] -
AC^{1} -
ACC^{0} -
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_{0}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
_{0}PP contains QMA, AWPP, and coC_{=}P. - A
_{0}PP is contained in PP. - If A
_{0}PP = PP then PH is contained in PP.

Kuperberg ([Kup09]) showed that A_{0}PP = SBQP.

##### AC: Unbounded Fanin Polylogarithmic-Depth Circuits

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

Then AC is the union of AC^{i} over all nonnegative i.

AC^{i} is contained in NC^{i+1}; thus, AC = NC.

Contains NL.

For a random oracle A, (AC^{i})^{A} is strictly contained in (AC^{i+1})^{A}, and (uniform) AC^{A} is strictly contained in P^{A}, with probability 1 [Mil92].

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

##### AC^{0}: 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^{0} [FSS84].

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

[LMN93] showed furthermore that functions with AC^{0} 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^{0}, [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^{0} contains NC^{0}, and is contained in QAC_{f}^{0} and MAC^{0}.

In descriptive complexity, uniform AC^{0} 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^{0} 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^{0}[m]: AC^{0} With MOD m Gates

Same as AC^{0}, 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^{0}[m] [Raz87] [Smo87]. It follows that, for any such m, AC^{0}[m] is strictly contained in NC^{1}.

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

See also: QAC^{0}[m].

##### AC^{1}: Unbounded Fanin Log-Depth Circuits

See AC.

##### ACC^{0}: AC^{0} With Arbitrary MOD Gates

Same as AC^{0}[m], but now the constant-depth circuit can contain MOD m gates for *any* m.

Contained in TC^{0}.

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^{0}.

There is no non-uniform ACC^{0} circuits of polynomial size for NTIMES[2^{n}] and no ACC^{0} 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^{0} and were recently discovered by [Wil11].

See also: QACC^{0}.

##### AH: Arithmetic Hierarchy

The analog of PH in computability theory.

Let Δ_{0} = Σ_{0} = Π_{0} = R. Then for i>0, let

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 . is the set of formula who are negation of formula.

##### AL: Alternating L

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

##### 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^{1}.

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

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

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

If AM contains coNP then PH collapses to Σ_{2}P ∩ Π_{2}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_{2}-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_{2}-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.

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

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

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

In particular, AP = ATIME(poly(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.

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

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

##### 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_{1},...,k_{r}) (r,k_{1},...,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

_{1},...,S

_{r}. Does there exist an assignment to S

_{1}of Hamming weight k

_{1}, such that for all assignments to S

_{2}of Hamming weight k

_{2}, 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].