Theoretical Computer Science
approximation-algorithms approximation-hardness pcp
Updated Fri, 24 Jun 2022 21:54:24 GMT

number of PCP queries


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 ?



Solution

I believe the best result (with regards to the number of queries) is still Hstad'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.

Comments (3)

  • +2 – 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. — May 22, 2013 at 16:31  
  • +0 – 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? — May 22, 2013 at 16:42  
  • +4 – @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. — May 22, 2013 at 21:41  

External Links

External links referenced by this document:

References