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.