Proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$

Question

I'm studying the PCP theorem.

While it is easy to prove that $\mathsf{P}=\text{PCP}(O(\log n),0)$ , proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$ i.e. PCP that uses $O(\log n)$ random bits and read 1 bit of the proof is less obvious, what I tried to do is to take some proof $\pi$ of length $n^{O(1)}$ (because effectively the message sent by the prover is bounded by $2^{r(n)}q(n)=2^{O(\log n)}=n^{O(1)}$) then try all the coin tosses each time the verifier read some bit of the message so if the proof is not correct we flip the bit in the proof!

Answer 1

By the basic equivalence of PCPs and MaxCSP problems, there exists a conjunction $C$ of polynomially many boolean literals, s.t.

$\exists \text{ proof } \pi$ which makes the verifier $V$ accept with probability $\geq p$ $\Leftrightarrow$ $\exists$ an assignment that satisfies at least a $p$ fraction of the literals in $C$.

So you just need to show that the following problem is polytime solvable: given a conjunction $C$ of boolean literals, what is the largest number of literals that can be simultaneously satisfied. That's a very easy problem.

The idea here is that a PCP with query complexity $q$ corresponds to some MaxCSP problem with arity $q$. If the PCP has completeness $c$ and soundness $s$, then the language accepted by the PCP is reducible to a promise version of an arrity $q$ MaxCSP problem where in a 'no' instance at most an $s$ fraction of the constraints can be satisfied, and in a 'yes' instance at least a $c$ fraction of the constraints can be satisfied. These reductions are standard, look up any reference on PCPs.

Answer 2

The PCP theorem states that $\mathrm{NP}=\mathrm{PCP}[O(\log n),O(1)]$. So showing that $\mathrm{PCP}[O(\log n), O(1)] \subseteq \mathrm{P}$ should be pretty difficult...