NP-Vollständigkeit

Unter den NP-Problemen sind jene besonders interessant, auf die sich alle anderen polynomiell reduzieren lassen. Dass es solche Probleme überhaupt gibt, ist die überraschende Aussage des Satzes von Cook-Levin. Eine große Zahl von NP-vollständigen Problemen gibt dem Praktiker die Möglichkeit, durch Vergleich Skalierungsprobleme in Aufgabenstellung in der Praxis rechtzeitig zu erkennen.