Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-034 | 23rd June 1998 00:00

A tight characterization of NP with 3 query PCPs



It is known that there exists a PCP characterization of NP
where the verifier makes 3 queries and has a {\em one-sided}
error that is bounded away from 1; and also that 2 queries
do not suffice for such a characterization. Thus PCPs with
3 queries possess non-trivial verification power and motivate
the task of determining the lowest error that can be achieved
with a 3-query PCP. Recently, Hastad has shown a tight
characterization of NP by constructing a 3-query PCP verifier
with ``error'' arbitrarily close to $1/2$. Unfortunately,
this verifier makes {\em two-sided} error and Hastad makes
essential use of this feature. One-sided error, on the
other hand, is a natural notion to associate with a proof
system, since it has the desirable property that every rejected
proof has a short counterexample. The question of determining
the smallest error for which there exists a 3-query PCP verifier
making one-sided error and accepting an NP-complete language,
however, remained open.

We resolve this question by showing that NP has a 3-query PCP
with a one-sided error that is arbitrarily close to $1/2$. This
characterization is {\em tight}, i.e., the error cannot be lower.
This result is in seeming contradiction with the results of
Trevisan and Zwick who show that in order to recognize an
NP-complete language, the error probability of a PCP verifier
making 3 {\em non-adaptive} queries and having one-sided error
must be at least $5/8$. We get around this bottleneck by
designing an {\em adaptive} 3-query PCP for NP. Our result
yields the first tight analysis of an adaptive PCP; and reveals
a previously unsuspected separation between the powers of adaptive
and non-adaptive PCPs.

Our design and analysis of adaptive PCPs can be extended to higher
number of queries as well and we give an example of such a proof
system with 5 queries. Our adaptive verifiers yield proof systems
whose error probabilities match those of previous constructions, while
also achieving one-sidedness in the error. This raises new questions
about the power of adaptive PCPs, which deserve further study.

ISSN 1433-8092 | Imprint