hardness of approximation
An approximation algorithm offers a deal: I cannot give you the exact best answer fast, but I can give you something provably close. A natural worry is whether you can always strike that deal. For some problems the disappointing answer is no: finding even a roughly-good answer is itself NP-hard. Hardness of approximation is the study of these limits — proving that, unless P = NP, no polynomial-time algorithm can approximate a given problem better than some specific ratio.
How can one prove that approximating is hard? The breakthrough tool is the PCP theorem (its own entry). Roughly, it lets us re-encode an NP problem so that there is a 'gap': yes-instances can be satisfied almost completely, while no-instances cannot be satisfied beyond some fraction, with nothing in between. Any algorithm that approximated the optimum closely enough would have to distinguish these two cases — and that distinction solves the original NP-complete problem exactly. So a good approximation algorithm would imply P = NP. This 'gap-creating' reduction is the heart of every inapproximability result.
The picture that emerges is rich and uneven, and worth taking seriously. Some problems (like metric TSP or vertex cover) approximate well; others approximate only up to a sharp threshold and no further (MAX-3SAT cannot be approximated beyond 7/8 unless P = NP, a tight result); and a few, like general graph coloring or maximum clique, cannot be approximated within any reasonable factor at all. The honest lesson is that 'just approximate it' is not a universal escape hatch from NP-hardness: for certain problems, approximation is provably as hard as exact solution.
For MAX-3SAT (satisfy as many clauses as possible), a trivial random assignment already satisfies 7/8 of the clauses on average. The striking PCP-based theorem says you cannot beat this: any polynomial-time algorithm guaranteeing better than a 7/8 fraction would imply P = NP. So 7/8 is not just easy — it is essentially the best achievable, a perfectly tight wall.
A 'gap' reduction (built on the PCP theorem) makes close approximation as hard as exact NP solution.
Inapproximability results are conditional: they say 'no good approximation exists UNLESS P = NP'. They do not, by themselves, prove P is not NP; they prove that beating a threshold is exactly as hard as the open P-vs-NP question.