# $\mathcal{MA}$ in terms of $\mathcal{PCP}$

The probabilistic proof system $\mathcal{PCP}[f(n),g(n)]$ is commonly referred to as a restriction of $\mathcal{MA}$, where Arthur can only use $f(n)$ random bits and can only examine $g(n)$ bits of the proof certificate sent by Merlin (see, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP).

However, In 1990 Babai, Fortnow, and Lund proved that $\mathcal{PCP}[poly(n), poly(n)] = \mathcal{NEXP}$, so its not exactly a restriction. What are the parameters ($f(n),g(n)$) for which $\mathcal{PCP}[f(n), g(n)] = \mathcal{MA}$?

If you want to restate the definition of MA in terms of PCP, you need another parameter for PCP, namely the proof length. MA is clearly the same as PCP with polynomial randomness, polynomial queries, and polynomial-length proofs. Usually the proof length in PCP is not restricted (that is, it is bounded only implicitly by randomness and queries), but this is insufficient to restate the definition of MA.

If you are looking for some characterization of the form MA = PCP(q(n), r(n)), which is not just the restatement of the definition of MA, then I do not think that any such characterization is known.

Under a hardness assumption, namely, that the complexity class $E = DTIME(2^{O(n)})$ requires circuits of exponential size, suffices to derandomize $MA$, so that $MA = NP$. In fact, the derandomization is to show that $BPP = P$ (see Impagliazzo-Wigderson or Sudan-Trevisan-Vadhan) . But since in $MA$ the verifier is a $BPP$ machine, we can replace it with a deterministic machine.

Thus, modulo this hardness assumption, $MA$ should have the exact same PCP characterization as $NP$. The complexity community seems to strongly believe that the hardness assumption is true, as well.

Edit: You might also want to take a look at Andy Drucker's Masters Thesis: "A PCP Characterization of $AM$": http://eccc.hpi-web.de/report/2010/019/.

Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf