Class Description

MA_EXP: Exponential-Time MA

Same as MA, except now Arthur is EXP instead of polynomial-time, and the message from Merlin can be exponentially long.

There is a problem in MA_EXP that does not have polynomial-size circuits [BFT98]. On the other hand, there is an oracle relative to which every problem in MA_EXP does have polynomial-size circuits.

[MVW99] considered the best circuit lower bound obtainable for a problem in MA_EXP, using current techniques. They found that this bound is half-exponential: i.e. a function f such that f(f(n))=2ⁿ. Such functions exist, but are not expressible using standard asymptotic notation.

Linked From

ALL: The Class of All Languages

Literally, the class of ALL languages.

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

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

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

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

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

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

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

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

More about...

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

More about...

MA: Merlin-Arthur

The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that

1. If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
2. If the answer is "no," then for all proofs Arthur accepts with probability at most 1/3.

Defined in [Bab85].

An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).

Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.

Also contained in Σ₂P ∩ Π₂P.

There exists an oracle relative to which BQP is not in MA [Wat00].

Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].

Shown in [San07] that MA/1 (that is, MA with 1 bit of advice) does not have circuits of size ${\displaystyle n^{k}}$ for any ${\displaystyle k>0}$. In the same paper, the result was used to show that MA/1 cannot be solved on more than a ${\displaystyle 1/2+1/{n^{k}}}$ fraction of inputs having length ${\displaystyle n}$ by any circuit of size ${\displaystyle n^{k}}$. Finally, it was shown that MA does not have arithmetic circuits of size ${\displaystyle n^{k}}$.

See also: MA_E, MA_EXP, OMA.

More about...