Theory of Computational Complexity, 2nd Edition

Chapter 11

Probabilistically Checkable Proofs and NP-Hard Optimization Problems

The notion of interactive proof systems may be extended to a more general notion of presenting short proofs whose correctness can be checked in probabilistic polynomial time. In this chapter, we present a new characterization for the class NP in terms of the notion of probabilistically checkable proofs. That is, the membership of an instance in a set in NP has a proof of a polynomially bounded length that can be verified by only checking randomly a constant number of bits. The proof uses the recently developed polynomial-time construction of expanders. The new characterization of NP has an important application to the study of the approximation to NP-hard combinatorial optimization problems. We present a number of combinatorial optimization problems that are not approximable within a constant factor of the optimal solutions if .

11.1 Probabilistically Checkable Proofs

We have studied in Chapter 10 the notion of interactive proof systems for problems in PSPACE. In this chapter, we make further detailed analysis of the power of interactive proof systems. In particular, we are interested in two additional complexity measures of interactive proof systems, namely, the number of random bits used by the verifier and the number of bits of the proofs the verifier actually reads. The number of random bits ...