# 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 ...

Get *Theory of Computational Complexity, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.