I am trying to show that a particular language $L$ in PCP(log,q) is also in P. The PCP protocol works as follows: log many random bits and checks at q positions in a polynomial length proof. The protocol accepts if two or more queries are 1. Assume that this has perfect completeness. I think one can handle randomness in P by usual methods. I am having problem with using the bound on queries to show that it is in P. How to show that $L$ can be recognized by a polytime algorithm? Can we somehow use maxSAT equivalent form for PCP?

  • $\begingroup$ I feel that some details are missing. Can you describe all details? $\endgroup$ – Yuval Filmus May 2 at 16:32
  • $\begingroup$ @Yuval Filmus Consider a language $L$ with polytime verifier $V$ and polylength proof $w$. Verifier reads $x$, tosses r=log(|x|) coins and reads q bits of proof. Then it decides to accept if at least 2 bits read are 1 rejects otherwise. For $x \in L$ there exists $w$ such that $V(x,w)$ = 1 with probability 1 . $x \notin L$ rejected with some constant probability at least. $\endgroup$ – Root May 2 at 16:43
  • $\begingroup$ Wouldn't the verifier always accept if $w$ consists entirely of 1s? In that case, $L$ just contains all words. $\endgroup$ – Yuval Filmus May 2 at 16:46
  • $\begingroup$ @Yuval Filmus I see your point. I also don't see $x$ and $w$ connected in some way which could be ok theoretically but doesn't make much sense what if we exclude the case where everything is 1 . $\endgroup$ – Root May 2 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.