Class Description

OMA: Oblivious MA

The class of functions computable in randomized polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of MA.

L is in OMA if there exists a randomized, polynomial time verifier V taking an input and a witness, so that:

1. There is a witness for each n of polynomial size, so that for any input of size n, if the input is is in L, then the verifier accepts on that input and the witness.
2. If the input is not in L, then for any witness, the verifier rejects on that input with probability at least 1/2.

NP is contained in OMA iff NP is in P/poly [FSW09].

EXP is contained in P/poly iff EXP = OMA [FSW09].

BPP is contained in OMA [GM15].

Implicit in [San07] that OMA/1 (that is, OMA with 1 bit of trusted advice) does not have circuits of size ${\displaystyle n^{k}}$ for any ${\displaystyle k>0}$.

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

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