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 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.