Theory of Computational Complexity, 2nd Edition

Notes on the Second Edition

The PCP characterization of the complexity class NP has been considered as one of the most important and insightful results in computational complexity theory. It was first proved in 1992, but the proof kept evolving in the past 20 years. Particularly, through the effort of Dinur and other researchers, we now have a combinatorial proof of this theorem that provides new different insight into this celebrated result. In the First Edition of this book, we presented the original proof. That proof was long and was based on algebraic coding theory, which made it hard to follow for students who are not familiar with this area. Due to the importance of the PCP theorem, in theory as well as in applications, we decided to replace the original proof by the new combinatorial proof that is based on the notion of expander graphs, a research area that has recently found many applications in computer science. We hope that the new proof will make this result more accessible to readers.

The work of the second author is partially supported by Aiming for the Top University Program of the National Chiao Tung University and Ministry of Education, Taiwan, R.O.C.

DING-ZHU DU

KER-I KO