Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey and Johnson's 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness.
De la rezultatele inițiale, mii de alte probleme s-au dovedit a fi NP-complete prin reducere la alte probleme, anterior demonstrate a fi NP-complete; multe dintre aceste probleme sunt colectate în cartea lui Garey⁠(d) și Johnson⁠(d) din 1979 intitulată Computers and Intractability: A Guide to the Theory of NP-Completeness⁠(d).