Komplexitätstheorie
Der Zweig der Informatik, der Probleme danach einteilt, wie viel Zeit und Speicher sie brauchen — nicht danach, wie schwer sie sich anfühlen.
Das Feld formalisierten Juris Hartmanis und Richard Stearns 1965, die ihm auch den Namen gaben und dafür 1993 den Turing Award erhielten. Probleme werden in Klassen sortiert: P ist, was sich in polynomieller Zeit lösen lässt, NP, wofür sich eine vorgeschlagene Lösung in polynomieller Zeit prüfen lässt, PSPACE, was mit polynomiellem Speicher auskommt, egal wie viel Zeit es braucht. Die Einordnung betrifft das Problem, nicht eine konkrete Implementierung — das unterscheidet sie von Big-O, das eine gegebene Implementierung beschreibt.
Der praktische Nutzen liegt darin, zu wissen, wann man aufhören sollte zu suchen. Ist ein Problem NP-vollständig, lohnt sich die Jagd nach einem exakten, effizienten Algorithmus nicht — dann wechselt man zu Heuristiken, Approximationen oder einer eingeschränkten Problemvariante. Die Kryptografie lebt umgekehrt davon, dass manche Probleme schwer sind: die gesamte Public-Key-Kryptografie beruht darauf, dass niemand einen schnellen Weg gefunden hat, große Zahlen zu faktorisieren.