Volume 1 (2005)
Article 7 pp. 119-148
Query Efficient PCPs with Perfect Completeness
Received: October 21, 2004
Revised: August 23, 2005
Published: September 28, 2005
Revised: August 23, 2005
Published: September 28, 2005
Download article from ToC site:
[PDF (274K)] [PS (483K)] [PS.GZ (135K)] [PS.ZIP (135K)]
[Source ZIP]
[PDF (274K)] [PS (483K)] [PS.GZ (135K)] [PS.ZIP (135K)]
[Source ZIP]
Keywords: Computational complexity, approximation algorithms, probablistically checkable proofs, PCP, inapproximability, amortized query bits, perfect completeness
Categories: complexity theory, probabilistically checkable proofs, PCP, approximation algorithms, inapproximability, Fourier analysis
ACM Classification: F.2.2,
AMS Classification: 68Q05
Abstract: [Plain Text Version]
For every integer k > 0, and an arbitrarily small
constant ε>0, we present a PCP characterization of
NP where the verifier uses logarithmic randomness, non-adaptively
queries 4k+k2 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-k2+ε.
In particular, the verifier
achieves optimal amortized query complexity of 1+δ for
arbitrarily small constant δ> 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+k2, the same as the number obtained by Samorodnitsky
and Trevisan. Finally we extend some of the results to PCPs over
non-Boolean alphabets.

Licensed under a Creative Commons License