The PCP theorem and hardness of approximation

PCP verifiers. A probabilistically checkable proof system for a language $L$ has a randomized verifier. It reads the input, tosses some random coins, reads a few positions of a written proof, and accepts or rejects. If the input is in $L$, some proof is accepted always (completeness). If not, every proof is accepted with probability at most $1/2$ (soundness). The PCP theorem (Arora–Safra; Arora–Lund–Motwani–Sudan–Szegedy, 1990s) says every problem in NP has such a verifier using only logarithmically many random bits and reading a constant number of proof positions. In short: $\mathsf{N}\mathsf{P}=\mathsf{P}\mathsf{C}\mathsf{P}[O(\log n),O(1)]$.