inapproximability
We have seen problems we can approximate well — vertex cover within 2, knapsack within (1 + epsilon). The natural next question is the pessimistic one: are there problems we provably CANNOT approximate well, no matter how clever we are? Inapproximability is the study of exactly these limits. It proves statements of the form 'unless P = NP, no polynomial algorithm can approximate this problem better than such-and-such factor' — a lower bound not on solving a problem exactly, but on approximating it at all.
The logic mirrors NP-hardness but aims at approximation. To show a problem is NP-hard, you reduce a known NP-hard problem to it. To show a problem is hard to APPROXIMATE, you build a special 'gap-producing' reduction: it maps every YES instance of an NP-hard problem to an instance whose optimum is large, and every NO instance to one whose optimum is small, with a guaranteed gap between 'large' and 'small'. Now suppose a polynomial algorithm could approximate within a factor smaller than that gap. Run it: its answer would land cleanly on one side of the gap or the other, letting you tell YES from NO instances of the original NP-hard problem in polynomial time — which is impossible unless P = NP. The width of the gap you can manufacture becomes the inapproximability factor you can prove. Concrete results: set cover cannot be approximated better than (1 - o(1)) ln n; MAX-3SAT cannot be approximated better than 7/8 + epsilon; and general (non-metric) TSP has no constant-factor approximation at all — each unless P = NP.
Why this matters: inapproximability tells you when to STOP searching for a better algorithm. If a problem is proven hard to approximate beyond factor c, then chasing factor c - 0.001 is chasing a proof that P = NP — a sign to redirect effort, perhaps to special cases, heuristics, or a different model. The honest caveats: these are conditional results, resting on P != NP (or sometimes the stronger Unique Games Conjecture); they are worst-case statements, so a 'hard' problem may still be easy on the instances you care about; and the deepest of these gap reductions are powered by a landmark theorem about proof verification — the PCP theorem — which is what made sharp inapproximability possible at all.
Set cover is a sharp case: greedy achieves about ln n, and inapproximability proves you cannot do essentially better — beating (1 - o(1)) ln n is NP-hard. So the greedy algorithm is not merely 'a' good algorithm; it sits right at the proven wall. No future cleverness will give a constant-factor set cover unless P = NP.
A gap-producing reduction turns 'beating factor c' into 'deciding an NP-hard problem' — so it is hard.
Inapproximability results are conditional and worst-case: they assume P != NP (or the Unique Games Conjecture) and forbid a good worst-case ratio, not good behavior on every instance. A problem hard to approximate in theory may still be tackled heuristically in practice.