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.