Complexity Theory, Proofs and Approximation
Johan Håstad
KTH, Stockholm, Sweden
![Complexity Theory, Proofs and Approximation cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fbooks%2Fcover-3.png&w=3840&q=90)
Download Chapter PDF
A subscription is required to access this book chapter.
Abstract
We give a short introduction to some questions in complexity theory and proceed to describe some recent developments. In particular, we discuss probabilistically checkable proofs and their applications in establishing inapproximability results. In a traditional proof the proof-checker reads the entire proof and decides deterministically whether the proof is correct. In a probabilistically checkable proof the proof-checker randomly verifies only a very small portion of the proof but still cannot be fooled into accepting a false claim except with small probability.