Eine Komplexitätsklasse fasst Probleme zusammen, die sich mit einer bestimmten Menge an Ressourcen (Rechenzeit oder Speicher) lösen lassen. Im Hessen-Abitur sind vor allem die Klassen P und NP sowie der Begriff der NP-Vollständigkeit relevant. Sie bilden die Grundlage dafür, warum manche Probleme „schwer“ sind – nicht weil wir zu dumm sind, sondern weil ihre Lösung wahrscheinlich unvermeidbar viel Zeit kostet.
Die Klasse P (polynomial time) enthält alle Entscheidungsprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit \( \mathcal{O}(n^k) \) gelöst werden können. Probleme in P gelten als effizient lösbar. Beispiele:
Die Klasse NP (nondeterministic polynomial time) enthält alle Entscheidungsprobleme, deren Lösung in polynomieller Zeit überprüft werden kann. Äquivalent: Probleme, die eine nichtdeterministische Turingmaschine in polynomieller Zeit lösen kann. Es gilt \( P \subseteq NP \).
Beispiele:
Ein Problem heißt NP-vollständig, wenn es in NP liegt und jedes andere NP-Problem sich in polynomieller Zeit auf es reduzieren lässt. NP-vollständige Probleme sind die „schwersten“ Probleme in NP. Stephen Cook zeigte 1971, dass SAT NP-vollständig ist (Satz von Cook). Heute kennt man tausende NP-vollständige Probleme: Travelling Salesman, Cliquen-Problem, Graphen-Färbung, Sudoku-Lösen u. v. m.
Die zentrale offene Frage der theoretischen Informatik lautet: Ist P = NP? Anders gesagt: Kann jedes Problem, dessen Lösung schnell überprüft werden kann, auch schnell gelöst werden? Die meisten Forscher vermuten nein, ein Beweis steht bis heute aus. Das Clay Mathematics Institute hat eine Million Dollar für eine Lösung ausgelobt. Würde \( P = NP \) bewiesen, wären grundlegende Verfahren der Kryptographie (z. B. RSA) sofort gebrochen.
Für NP-vollständige Probleme gibt es heute keine Algorithmen, die deutlich besser als exponentiell laufen. In der Praxis verwendet man Heuristiken (Greedy, Simulated Annealing), Approximationsalgorithmen oder Branch-and-Bound, um in akzeptabler Zeit gute (nicht zwingend optimale) Lösungen zu finden.
NP wird oft falsch als „nicht-polynomiell“ gelesen – richtig ist nondeterministic polynomial. Aus „NP“ folgt nicht, dass das Problem unlösbar ist; auch alle P-Probleme sind in NP. Ein Problem ist nur dann NP-schwer, wenn man es aus NP-vollständigen Problemen ableitet, nicht umgekehrt.
Zusammenfassung: P enthält effizient lösbare Probleme, NP enthält effizient verifizierbare Probleme, NP-vollständige Probleme sind die schwersten in NP. P = NP ist ungelöst.
Abitur-Tipp: Im Abitur reicht es zu erklären, was P, NP und NP-vollständig formal bedeuten und ein Beispiel pro Klasse zu nennen.