MA gets its name from the Arthur-Merlin games developed by Babai. MA is an interactive proof system where the all-powerful Merlin sends a message that is verified by a probabilistic Arthur. Here is a formal definition.

A language L is in MA if there is a probabilistic polynomial-time machine M and a polynomial p such that for all strings x,

- If x is in L then there is a w, |w|=p(|x|) and M(x,w) accepts with probability at least 2/3.
- If x is not in L then for all w, |w|=p(|x|), M(x,w) accepts with probability at most 1/3.

The w is a proof that Merlin can write down and Arthur can verify years later without further interaction from Merlin. Sometimes MA is called the class of languages with publishable proofs.

Despite the naturalness of the class, there are no known natural problems in MA not known to be in NP∪BPP.

MA contains NP and BPP and also NP^{BPP}. MA is
contained in its cousin class AM and thus BPP^{NP}. MA is also
contained in many of the same classes BPP is contained in, including
S_{2}, ZPP^{NP},
Σ_{2}∩Π_{2} and PP. There are oracles
where AM is not contained in these classes. Also none of these
containments are tight in all relativized worlds.

If L is checkable and has polynomial-size circuit then L is in MA. I will leave the definition of checkable to another post but this implies

_{EXP}does not have polynomial-size circuits. MA

_{EXP}is like MA with polynomials replaced with exponentials.

A strong pseudorandom generator that derandomizes probabilistic
circuits will also derandomize MA to NP. Using the result of
Impagliazzo-Wigderson we get: If E require 2^{ε n}
size circuits for some ε>0 then MA = NP.

The quantum version of MA, QMA has gotten some recent attention. Here Merlin sends entangled quantum bits and Arthur does quantum transformations and measurements. We will discuss QMA another day when it has its turn as complexity class of the week.

## No comments:

## Post a Comment