Summary The gap technique Proof Minimum graph coloring Inapproximability of graph coloring Inapproximability of bin paking TSP Inapproximability of TSP The NPO world (unless P=NP) Deterministically checkable proofs Probabilistically checkable proofs PCP [r,q] The PCP theorem Inapproximability of satisfiability Maximum clique Product graphs Self-improvability of clique Inapproximability of maximum clique The NPO world
