The computational intractability of NP-hard problems has occupied the minds of many computer theorists ever since Cook and Levin introduced them to computer science in the early 1970s. Karp’s subsequent formulation of a theory of NP-completeness and the resulting excitement about discovering such intractable problems led to the seminal publication of Garey and Johnson, which compiled all known NP-complete problems in the late 1970s. However, researchers soon ran out of steam, especially since they realized that many reasonable problems in theoretical computer science are computationally intractable.
To sidestep the computational intractability of several optimization problems, it was natural to look for near-optimal, as opposed to optimal, solutions. This approach is successful for some problems, such as bin-packing, but unsuccessful for others, such as the Euclidean traveling salesman problem, because approximation problems can also be computationally intractable. This is related to the problem of verification of proofs, which has always been central in all mathematical investigations. It is even more important in computer science, where one is confronted with the task of verifying the correctness of programs with thousands of lines of code. A simple solution to this is offered by the “busy software supervisor” paradigm: allow access to random parts of the code and accept probabilistic guarantees from the verifier.
This book focuses on a theory of hardness of approximation problems, and efficient checking of proofs. Based on the author’s 1992 doctoral dissertation, it describes a general technique for establishing the computational intractability of approximation problems under the assumption that P ≠ NP. Approximate hardness is established for all complete problems in the complexity class max -SNP, which includes Euclidean traveling salesman and Euclidean Steiner tree problems. These techniques are applicable elsewhere to problems such as chromatic number, shortest vector in a lattice, and set cover.
The efficiently verifiable proofs constructed rely on the structural properties of low-degree polynomials. Properties of these functions are explored by examining questions on testing and correcting:
Testing: Given an oracle for a function f, is f close to a low-degree polynomial?
Correcting: Given an oracle for a function f that is close to a low-degree polynomial g, is it possible to efficiently reconstruct the value of g on any given input using an oracle for f?
By combining results from coding theory with algorithmic techniques on pairwise independent sampling, the author gives efficient randomized algorithms for the two problems above.
Proof and verification systems have evolved to respond to the needs of present-day computer science in ways that would have pleasantly surprised even Frege, Hilbert, and Gödel. The work reported here is expected to have a significant effect on theoretical computer science and mathematics.
There is a lot of material to reflect about in this short book. Its six chapters are “Introduction,” “On the Resilience of Polynomials,” “Low-degree Tests,” “Transparent Proofs and the Class PCP,” “Hardness of Approximations,” and “Conclusion.” There is also a useful, extensive bibliography and three appendices. The writing is focused, pleasant, and quick-moving. Many proofs are omitted, but the book will still be suitable for research-oriented seminars.
