Class Description

MA_E: Exponential-Time MA With Linear Exponent

Same as MA, except now Arthur is E instead of polynomial-time.

If MA_E = NEE then MA = NEXP ∩ coNEXP [IKW01].

Linked From

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

If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
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 $n^{k}$ for any $k>0$ . In the same paper, the result was used to show that MA/1 cannot be solved on more than a $1/2+1/{n^{k}}$ fraction of inputs having length $n$ by any circuit of size $n^{k}$ . Finally, it was shown that MA does not have arithmetic circuits of size $n^{k}$ .

See also: MA_E, MA_EXP, OMA.

More about...

NEE: Nondeterministic EE

Nondeterministic double-exponential time with linear exponent (i.e. NTIME(2^{2^O(n)})).