Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-476-94

Authors:

Date:

October 1994

Pages:

166

Download Formats:

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.