<p>I believe the best result (with regards to the number of queries) is still <a href="http://csce.uark.edu/~dapon/lib/Hastad.pdf" rel="nofollow">Håstad's 3-query PCP</a>. So if you choose at least 3, then it's a definite yes.</p>

<p><a href="http://www.cs.washington.edu/education/courses/cse533/05au/lecture16.pdf" rel="nofollow">These lecture slides</a> might be a bit more useful as they cut straight to the chase.</p>

CC BY-SA 3.0
2013-05-22T16:31:14.577Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-05-22T16:42:52.940Z
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?
Sasho Nikolov
CC BY-SA 3.0
2013-05-22T21:41:41.007Z
@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.
Or Meir
CC BY-SA 3.0
2013-05-22T11:54:50.420Z
2013-05-22T11:54:50.420Z
Luke Mathieson
<p>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 ?  </p>

<approximation-algorithms><approximation-hardness><pcp>
number of PCP queries
Fayez Abdlrazaq Deab
# number of PCP queries

(Asked by: username_0 on 2013-05-22)

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 ?

**Tags:** approximation-algorithms, approximation-hardness, pcp


---

## 1 answers

### Answer by username_1 on 2013-05-22. Score: 3 | Accepted answer

I believe the best result (with regards to the number of queries) is still [Håstad's 3-query PCP](http://csce.uark.edu/~dapon/lib/Hastad.pdf). So if you choose at least 3, then it's a definite yes.

[These lecture slides](http://www.cs.washington.edu/education/courses/cse533/05au/lecture16.pdf) might be a bit more useful as they cut straight to the chase.

> **Comments:**
> **username_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.  
> **username_2**: 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?  
> **username_3**: @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.  

---

