Sin embargo David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión restringida de optimización que es no aproximable a menos que P = NP, demostrando que la versión de la reducción, dada por Karp, generaliza un tipo específico de reducción por aproximación.