Résumé: We show that the NP-Complete language 3SAT has a PCP verifier that makes two queries to a proof of almost-linear size and achieves subconstant probability of error e = o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query. The number of bits representing a symbol in the proof depends only on the error e. Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size. There were also PCP Theorems with subconstant error and almost-linear size, but a constant number of queries that is larger than 2.

Langue: Anglais