Skip to Main Content
Theory of Computational Complexity, 2nd Edition
book

Theory of Computational Complexity, 2nd Edition

by Ding-Zhu Du, Ker-I Ko
June 2014
Intermediate to advanced content levelIntermediate to advanced
512 pages
17h 55m
English
Wiley
Content preview from 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 c11-math-0001.

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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Theory of Computation

Theory of Computation

George Tourlakis

Publisher Resources

ISBN: 9781118594971Purchase book