Theory of Computing
-------------------
Title     : Query Efficient PCPs with Perfect Completeness
Authors   : Johan Haastad and Subhash Khot
Volume    : 1
Number    : 7
Pages     : 119-148
URL       : https://theoryofcomputing.org/articles/v001a007

Abstract
--------
For every integer k > 0, and an arbitrarily small constant 
epsilon>0, we present a PCP characterization of NP where 
the verifier uses logarithmic randomness, non-adaptively
queries 4k+k^2 bits in the proof, accepts a correct proof 
with probability 1, i.e., it has perfect completeness, and 
accepts any supposed proof of a false statement with 
probability at most 2^{-k^2}+epsilon. In particular, the  
verifier achieves  optimal amortized query complexity of 
1+delta for arbitrarily small constant delta > 0. Such a 
characterization was already proved by Samorodnitsky and 
Trevisan (STOC 2000), but their verifier loses perfect 
completeness and their proof makes an essential use of
this feature.

By using an adaptive verifier, we can decrease the number 
of query bits to 2k+k^2,  the same as the number obtained by
Samorodnitsky and Trevisan.   Finally we extend some of 
the results to PCPs over non-Boolean alphabets.