Theorie, die sich mit Problemen, die NP-vollständig sind, befaßt.

Es ist noch eine offene Frage, ob die Komplexitätsklassen NP und P verschieden sind.

Allgemein wird von der NP≠P-Hypothese ausgegangen, da aus der Annahme NP=P sehr unwahrscheinliche Folgerungen abgeleitet werden können. Falls NP≠P, kann es für NP-vollständige und NP-schwere Probleme (NP-schweres Problem) keine polynomialen Algorithmen (Polynomialer Algorithmus) geben. Für Probleme in NP ist der Nachweis der NP-Vollständigkeit aus heutiger Sicht das stärkste Indiz, daß das Problem nicht in P enthalten ist. Erstmals wurde im Satz von Cook (Cook, Satz von) ein Problem als NP-vollständig nachgewiesen. Zum Nachweis der NP-Vollständigkeit eines Problems in NP genügt es, eine Polynomielle Zeitreduktion von einem NP-vollständigen Problem auf das untersuchte Problem anzugeben. Die Liste wichtiger bekannter NP-vollständiger Probleme enthält einige tausend Einträge.

Die NP-Vollständigkeitstheorie ist das, auch für Anwendungen, wichtigste Teilgebiet der Komplexitätstheorie.