View article

The PCP theorem [Arora et al. 1998; Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length n by PCPs of length n · poly log n that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to n^ε, then one can construct PCPs of length O(n) for circuit-SAT, and PCPs of length O(tlog t) for any language in NTIME(t).

More specifically, for any ε > 0, we present (nonuniform) probabilistically checkable proofs (PCPs) of length 2^O(1/ε) · n that can be checked using n^ε …