
Zur Zeit weiß man von über 2000 Problemen, daß sie NP-vollständig sind (vgl. Kapitel 41). Seit 1972, als Stephen Cook feststellte, daß das Erfüllbarkeitsproblem NP-vollständig ist, haben Wissenschaftler einen ständigen Strom von Ergebnissen veröffentlicht, in denen die NP-Vollständigkeit für andere Probleme gezeigt wird. Die Liste NP-vollständiger Probleme wächst ständig.