Before introducing probabilistically checkable proofs, I shortly give an overview of the historical development in the field of inapproximability results which are closely related to PCPs. A foundational paper from Johnson in 1974 states approximation algorithms and inapproximability results for Max SAT, Set Cover, Independent Set, and Coloring.While the decision problems for various problems, such as Max SAT, Set Cover, Independent Set, and Coloring, were shown to be NP-hard by Cook, Levin and
Karp, it was difficult to show approximability and inapproximability results with the known reductions.
To prove inapproximability results, there was a new model for NP necessary, this evolved from works on multi-provers interactive proofs from Ben-Or and Goldwasser. In 1991, Feige and Goldwasser created this new model and showed new inapproximability
results with this model. This new model was later on called PCP. In 1992, Arora could prove the PCP Theorem which made PCP easier and useful to apply for many inapproximability problems. Since then, many computer scientists could prove and improve many inapproximability results creating tight results for many NP-hard problems. In 2005, Dinur has published a new proof for the PCP Theorem. This will be introduced in the paper from Bernhard Vesenmeyer, the necessary tools for this proof will be introduced in the sections about constraint graphs and expander graphs.