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!


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.

  • $\begingroup$ thank you for the great help ... I am trying to understand these things and you help me a lot ... although I knew the reduction but I didn't know it's usefulness thank to you know I understand it very good ... $\endgroup$ – Fayez Abdlrazaq Deab May 26 '13 at 9:22
  • $\begingroup$ I am glad you found this helpful! $\endgroup$ – Sasho Nikolov May 26 '13 at 22:15

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

  • $\begingroup$ I didn't mean O(1) but just 1 query $\endgroup$ – Fayez Abdlrazaq Deab May 25 '13 at 21: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.