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 ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Apr 28, 2018 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
    Commented Apr 28, 2018 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
    Commented Apr 28, 2018 at 21:46
  • $\begingroup$ Aaaah, that's what I've been missing. Thank you, makes sense now. $\endgroup$
    – Askannz
    Commented Apr 29, 2018 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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