TR98-034 Authors: Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

Publication: 24th June 1998 13:38

Downloads: 1520

Keywords:

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.