Probabilistic Checking of Proofs and Hardness of Approximation Problems
Report ID: TR-476-94Author: Arora, Sanjeev
Date: 1994-11-00
Pages: 166
Download Formats: |Postscript|
Abstract:
This report is a revised form of a dissertation submitted by the author at UC Berkeley in Fall 1994. It establishes a surprising new characterization of NP, the class of languages for which membership proofs can be checked in polynomial time deterministically. The class NP is exactly the set of languages for which membe rship proofs can be checked by a probabilistic polynomial time verifier that examines a constant number of bits in the proof, and uses $O(log n)$ random bits, where $n$ is the size of the input. This characterization of NP underlies new results on the hardness of approximating a host of optimization problems. Among the problems proved hard to approximate are classical optimization problems such as Clique, Independent Set, Max-Sat, Vertex Cover, every MAX-SNP-hard problem, Nearest Lattice Vector, Nearest Codeword, and Shortest Lattice Vector (only the version using the $ell_{infty}$ norm). The report includes a survey of related results in these areas.