Probabilistic Checking of Proofs and Hardness of Approximation Problems

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.