# When and How Can We Compute Approximately Optimal Solutions to Intractable Computational Problems?

The discovery of NP-completeness by computer scientists in the 1970s showed that many computational problems in a variety of disciplines do not have efficient algorithms (assuming the classes P and NP are different, as is widely believed). This was a profound discovery. However, in practice it often suffices to solve problems approximately: say, to obtain a solution of cost within 10% of optimum. Can efficient algorithms find approximately optimal solutions? The classical theory of NP-completeness didn’t address or preclude this possibility. Research in the past two decades has answered the approximability issue for a large subset of NP-complete problems. We know the precise approximation threshold that can be achieved by efficient algorithms, and also know that improving upon that threshold is no easier than exact optimization. The former is the domain of “approximation algorithms,” and the latter of the theory of “probabilistically checkable proofs.” This theory makes connections with a host of other disciplines and yields surprising results such as the PCP Theorem, which states that mathematical proofs can be checked by examining a constant number of bits in them (this constant is independent of the size of the proof).

Chapter 8 on NP-completeness from Algorithms by Dasgupta, Papadimitriou & Vazirani

NP-completeness: A Retrospective

The Approximability of NP-hard Problems