15
$\begingroup$

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}$?

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

Sudan-Trevisan-Vadhan: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

$\endgroup$
11
$\begingroup$

Tsuyoshi Ito answered the question literally, but I wanted to comment about the semantics of MA and PCP and how they differ.

MA is the probabilistic version of NP, i.e., the verifier gets to also use poly-many random bits.

In PCP we may refer to the "randomness" of the verifier, but usually the randomness is logarithmic in the running time of the verifier, i.e., the verifier could have tried all possible random strings by itself. In other words, this "randomness" doesn't buy the verifier any computational power, unlike the case of MA.

[So what is this "randomness" good for? The point of PCP is that for probabilistic verification a single test --with a constant number of queries to the proof-- suffices]

Addendum (following Tsuyoshi's comment): In PCP characterizations of NP the verifier's running time can be made poly-logarithmic, and, similarly, in characterizations of NEXP the verifier's running time is polynomial. Nonetheless, the randomness in PCP constructions is typically used only to pick a test (in characterizations of NP, out of poly-many tests, and in characterizations of NEXP, out of exponentially many) and not to help with the computation. Moreover, in MA, the proof is of polynomial size, while in characterizations of NEXP, the proof is of exponential size.

$\endgroup$
  • $\begingroup$ I agree that we give the verifier only logarithmic randomness in the PCP theorem for NP so that this randomness alone will not buy the verifier any computational power. However, it seems that you are making a more general claim than this by stating “usually the randomness is logarithmic in the running time of the verifier,” which I am afraid is too general to be true. Usually we do not allow the verifier to spend exponential time even when we consider PCP(poly,poly)=NEXP (although doing so does not change this equality), and this seems to be a counterexample to your statement. $\endgroup$ – Tsuyoshi Ito Sep 23 '12 at 2:49
  • 1
    $\begingroup$ Thanks for the followup! I think that now I understand better what you mean by saying that MA and PCP use randomness differently. $\endgroup$ – Tsuyoshi Ito Sep 24 '12 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.