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

<p>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.</p>

CC BY-SA 3.0
2018-04-28T13:20:45.697Z
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.
Askannz
CC BY-SA 3.0
2018-04-28T14:39:12.863Z
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.
Askannz
CC BY-SA 3.0
2018-04-28T21:46:31.713Z
@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.
WuHongxun
CC BY-SA 3.0
2018-04-29T02:48:26.947Z
Aaaah, that's what I've been missing. Thank you, makes sense now.
Askannz
CC BY-SA 3.0
2018-04-28T12:32:12.857Z
2018-04-28T12:32:12.857Z
WuHongxun
<p>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}$ ?</p>

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

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

<p>Is this proof correct ?</p>

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

(Asked by: username_0 on 2018-04-28)

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 ?

**Tags:** complexity, pcp

---

## 1 answers

### Answer by username_1 on 2018-04-28. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: @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.  
> **username_0**: Aaaah, that's what I've been missing. Thank you, makes sense now.  

---

