# Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?

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 ?

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.
• @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. Apr 28 '18 at 21:46