1
$\begingroup$

we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?

$\endgroup$
3
$\begingroup$

I believe the best result (with regards to the number of queries) is still Håstad's 3-query PCP. So if you choose at least 3, then it's a definite yes.

These lecture slides might be a bit more useful as they cut straight to the chase.

$\endgroup$
3
  • 2
    $\begingroup$ There definitely exist 2-query PCPs. For example, Dinur's proof shows a hardness gap for 3-coloring, which corresponds to 2-query PCP with alphabet size 3. $\endgroup$ – Sasho Nikolov May 22 '13 at 16:31
  • $\begingroup$ More generically, the canonical label cover problem corresponds to a 2-query PCP with constant alphabet size. And since Max-E2-SAT is NP-hard to approximate, doesn't this imply a 2-query alphabet size 2 PCP? $\endgroup$ – Sasho Nikolov May 22 '13 at 16:42
  • 4
    $\begingroup$ @SashoNikolov: You are right that this NP-hardness implies a PCP with two queries and alphabet size 2, but this PCP will not have perfect completeness. A PCP with alphabet size 2 can not have both perfect completeness and 2 queries, since the satisfiability of 2-CNF is in P. $\endgroup$ – Or Meir May 22 '13 at 21:41

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.