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.
David Zuckerman⁠(d) a arătat însă în 1996 că toate aceste 21 de probleme au o versiune optimizată cu constrângeri care este imposibil de aproximat cu orice factor constant dacă P ≠ NP, arătând că abordarea lui Karp asupra reducerii se generalizează la un anumit tip de reducere a aproximabilității.