Probabilistically Checkable Proofs with Low Amortized Query Complexity

The error probability of Probabilistically Checkable Proof (PCP) systems can be made exponentially small in the number of queries by using sequential repetition. In this paper we are interested in determining the precise rate at which the error goes down in an optimal protocol, and we make substantial progress toward a tight resolution of this question. A PCP verifier uses ¯ q amortized query bits if, for some t, it makes ¯ qt queries and has error probability at most 2 \Gammat . A PCP characterization of NP using 2:5 amortized query bits is known [25], and, unless P=NP, no such characterization is possible using 1 amortized query bits [7]. We present a PCP characterization of NP that uses roughly 1.5 amortized query bits. Our result has two main implications. Separating PCP from 2-Provers 1-Round. In the 2-Provers 1-Round (2P1R) model the verifier has access to two oracles (or provers) and can make one query to each oracle. Each answer is a string of l bits (l is called the answer ..