0
$\begingroup$

Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ?

I have found a proof for this statement but something feels wrong about it. Here it goes :

Let $L \in \textbf{PCP}[poly(n), O(1)]$. There is a verifier $V$ for $L$ which flips $poly(n)$ random coins and reads $q$ bits from the certificate, where $q$ is a constant.

The proof query of $q$ bits can return $2^q$ possible values. My idea is to build a $\textbf{coRP}$ algorithm $V'$ for $L$ by simulating $2^q$ copies of $V$, where each copy is given a different answer to the certificate query. $V'$ accepts if at least one of the copies of $V$ accepts.

If the input is in $L$ then there exists a certificate so that $V$ accepts with perfect completeness. The queried bits from that certificate are necessarily in our $2^q$ possible values, so at least one of the simulated copies of $V$ accepts with perfect completeness.

If the input is not in $L$, then all copies have probability < 1 of accepting. Thus $V'$ has some probability $\rho < 1$ of accepting.

Using amplification, we can then boost $\rho$ to $\frac{1}{2}$ to match the definition of $\textbf{coRP}$.

Is this proof correct ?

$\endgroup$
3
$\begingroup$

Recall PCP theorem, $PCP(log(n), 1)$ is NP already and actually $PCP(poly(n),1)$ is $NEXP$.

The problem of your proof is that you cannot simulate a coRP algorithm on a string with length only $2^q$. Though it will only access q bits, the bits it accesses to depend on the random coins. You should not think of a specific coin outcome but all of them on a input. That is basically why your proof doesn't work.

$\endgroup$
  • $\begingroup$ Thank you. So if I understand correctly, the verifier is reading the certificate from its input tape, but since it is expecting a certain length we cannot cheat it by writing only the bits it wants. $\endgroup$ – Askannz Apr 28 '18 at 13:20
  • $\begingroup$ If the verifier was making only one query, would that work then ? We could simulate two copies of the verifier : for the first copy, the certificate is filled with zeros, and for the second, the certificate is filled with ones. $\endgroup$ – Askannz Apr 28 '18 at 14:39
  • 2
    $\begingroup$ @Askannz You can regard $PCP(poly(n), 1)$ as $\exists_x$ for most of $y$, $M(x, y)$ accepts. Here y is the coin you toss. So most of y have to be correct simultaneously. Since some y accept when it reads 1 and some accept when it reads 0, You cannot trick it that way. $\endgroup$ – WuHongxun Apr 28 '18 at 21:46
  • $\begingroup$ Aaaah, that's what I've been missing. Thank you, makes sense now. $\endgroup$ – Askannz Apr 29 '18 at 2:48

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.