How NP got a new definition: a survey of probabilistically checkable proofs

Abstract

We survey a collective achievement of a group of researchers: the PCP Theorems. They give new definitions of the class \np, and imply that computing approximate solutions to many \np-hard problems is itself \np-hard. Techniques developed to prove them have had many other consequences.

Cited by in corpus (5)

• Approximation thresholds for combinatorial optimization problems
• Unique Decoding of Explicit $\epsilon$-balanced Codes Near the Gilbert-Varshamov Bound
• List Decoding of Direct Sum Codes
• The PCP-like Theorem for Sub-linear Time Inapproximability
• PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability