A survey of optimal PCP characterizations of NP
Luca Trevisan · 2002
Probabilistically checkable proofs (PCPs) define a model of computation that is quite interesting in its own right, and that is an extremely powerful tool to study the complexity of finding approximate solutions for combinatorial optimization. Since U. Feige et al. (1996) suggested a connection between proof-checking and approximation, this connection has been generalized and exploited to an amazing extent. In this paper we focus on efficient PCP constructions in five settings, for three of which essentially tight results are known, with useful applications, and for two of which tight results are still exciting open questions.