Complexity Theory, Proofs and Approximation

  • Johan Håstad

    KTH, Stockholm, Sweden
Complexity Theory, Proofs and Approximation cover
Download Chapter PDF

A subscription is required to access this book chapter.


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.