5
$\begingroup$

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!

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\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$ May 26, 2013 at 9:22
  • $\begingroup$ I am glad you found this helpful! $\endgroup$ May 26, 2013 at 22:15
3
$\begingroup$

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

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