How NP got a new definition: a survey of probabilistically checkable proofs
Sanjeev Arora · arXiv (Cornell University) · 2003
We survey a collective achievement of a group of researchers: the PCP Theorems. They give new definitions of the class p, and imply that computing approximate solutions to many p-hard problems is itself p-hard. Techniques developed to prove them have had many other consequences.