In his 1972 paper, "Reducibility Among Combinatorial Problems",[1] Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete[2] (also called the Cook-Levin theorem) to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete.
Karp's 21 problems are shown below, many with their original names.
As time went on it was discovered that many of the problems can be solved efficiently if restricted to special cases, or can be solved within any fixed percentage of the optimal result.
However, David Zuckerman showed in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within any constant factor unless P = NP, by showing that Karp's approach to reduction generalizes to a specific type of approximability reduction.
[3] Note however that these may be different from the standard optimization versions of the problems, which may have approximation algorithms (as in the case of maximum cut).