Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-034 | 23rd June 1998 00:00

#### A tight characterization of NP with 3 query PCPs

TR98-034
Authors: Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan
Publication: 24th June 1998 13:38
Keywords:

Abstract:

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

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

ISSN 1433-8092 | Imprint