Sanjeev Arora:
Probabilistic Checking of Proofs and Hardness of Approximation Problems
Abstract:
Several recent results show that computing even approximate solutions to many NP-hard optimization problems is NP-hard. At the heart of these results are new probabilistic ways of looking at the class NP.
This book, a revised version of the author's Ph.D. dissertation, is a survey of this area. It contains: (i) a self-contained proof of the result NP = PCP (log n,1) (ii) a fairly extensive discussion (with proofs) of results about hardness of approximating NP-hard problems (iii) a survey of applications of probabilistically checkable proofs, and (iv) a list of open problems about PCPs and hardness of approximations.
Chapter notes at the end of each chapter give a historical account of how the ideas in that chapter evolved, as well as pointers for further reading.
The survey was completed in the second half of 1994 and does not contain results proved since then. Also, it is not a finished book. Comments/bug reports are most welcome.
Keywords:
NP, NP-completeness, Approximation, Approximation Algorithms, Probabilistic Checking of Proofs, Interactive Proofs, Randomness.
Download
PDF-file of the entire book.
Copyright (c) 1994,
Sanjeev Arora
