Die Komplexitätstheorie ist die Theorie zur Bestimmung der Ressourcen, die zur Lösung eines Problems notwendig sind.

Die Komplexitätstheorie und die Theorie effizienter Algorithmen bilden die beiden Seiten einer Medaille. Ein algorithmisches Problem kann als gelöst gelten, wenn ein Algorithmus bekannt ist, der nicht wesentlich mehr Ressourcen verbraucht, als zur Lösung des Problems als notwendig nachgewiesen worden sind. Der Nachweis unterer Schranken für die zur Lösung eines Problems benötigten Ressourcen erweist sich als sehr schwierig, da für alle Algorithmen, die das Problem lösen, nachgewiesen werden muß, daß sie nicht mit weniger Ressourcen auskommen. Nur für recht einfache Situationen ist der Nachweis guter unterer Schranken gelungen. Ansonsten wird die Komplexität eines Problems relativ zu anderen Problemen gemessen. Die Hypothese, daß ein Problem nicht effizient, z. B. in polynomieller Zeit, lösbar ist, kann untermauert werden, indem aus der gegenteiligen Annahme Folgerungen abgeleitet werden, die im Widerspruch zu gut etablierten Hypothesen stehen.

Das wichtigste Teilgebiet der Komplexitätstheorie, das gleichzeitig den größten Einfluß auf die Entwicklung von Informatik und Mathematik hatte, ist die Theorie der NP-Vollständigkeit. Die Klasse der NP-vollständigen und darüber hinaus der gleichzeitig NP-leichten und NP-schweren Probleme enthält Probleme, die entweder alle in polynomieller oder alle nicht in polynomieller Zeit lösbar sind, d. h. entweder ist NP=P (siehe NP, P) oder NP≠P. Die Hypothese NP≠P ist sehr gut begründet, da aus NP=P recht absurde, aber noch keine widerlegten Konsequenzen abgeleitet werden können. Die NPVollständigkeit eines Problems ist heutzutage für typische algorithmische Probleme das stärkste erreichbare Indiz dafür, daß sie nicht in polynomieller Zeit lösbar sind.

Die Theorie der NP-Vollständigkeit bezieht sich auf die Möglichkeit oder Unmöglichkeit von Algorithmen mit polynomieller Rechenzeit. Für andere Ressourcentypen oder -grenzen wurden ähnliche Theorien entwickelt, z. B. für den nötigen Speicherplatzbedarf. Der Möglichkeit von Algorithmen, die eine Pseudo-polynomielle Rechenzeit haben, also für Eingaben mit kleinen Zahlen effizient sind, steht der Begriff streng NP-vollständiges Problem gegenüber.

Bei einem Optimierungsproblem, das NPschwer ist, gibt es aus algorithmischer Sicht den Ausweg, nur fast optimale Lösungen zu berechnen. Ein neuerer Meilenstein der Komplexitätstheorie besteht in der Entwicklung der PCP-Theorie, mit der unter der Annahme NP≠P (oder stärkerer Annahmen) für viele Optimierungsprobleme ausgeschlossen werden kann, daß es für sie polynomielle Algorithmen gibt, die fast optimale oder auch nur gute Lösungen garantieren.

Die Komplexitätstheorie hat auf alle Entwicklungen von neuen Algorithmentypen reagiert. Zu den verschiedenen Typen randomisierter Algorithmen (randomisierter Algorithmus) gehören die Komplexitätsklassen ZPP, RP, BPP und PP. Auch für die von Parallelrechnern benötigten Ressourcen gibt es einen Zweig der Komplexitätstheorie.

Algorithmen modellieren Softwarelösungen und sollen Probleme für Eingaben beliebiger Länge lösen. Bei Hardwareproblemen ist die Eingabelänge vorgegeben, und jede Boolesche Funktion ist berechenbar. Hierzu gehört die Komplexitätstheorie für nicht-uniforme Berechnungsmodelle wie Schaltkreise oder Branchingprogramme (Bran-chingprogramm).

Für alle betrachteten Situationen konnten mit der Komplexitätstheorie fundierte Hypothesen gebildet werden, mit denen Probleme als schwer, d. h. nicht effizient berechenbar klassifiziert werden können. Derartige negative Resultate geben bei der Entwicklung von Algorithmen Hinweise, welche Algorithmentypen zur Problemlösung ungeeignet oder geeignet sind.

Die Komplexität eines Problems ist jedoch nicht nur ein für die algorithmische Lösung wichtiges Merkmal, sondern auch ein darüber hinaus reichendes Strukturmerkmal. Der strukturelle Zweig der Komplexitätstheorie untersucht Beziehungen zwischen verschiedenen Komplexitätsklassen und den Abschluß von Komplexitätsklassen gegenüber Operationen auf den in ihnen enthaltenen Problemen. Zentrale Aspekte wie der Nichtdeterminismus werden auf allgemeine Weise untersucht. Die Klasse algorithmisch schwieriger Probleme wird noch weiter strukturiert, z. B. kann durch Einordnung eines Problems in die Polynomielle Hierarchie der Schwierigkeitsgrad stärker spezifiziert werden. Ein Problem kann auch dann als besonders komplex gelten, wenn es als Orakel, also als beliebig benutzbares Modul, besonders viele andere schwierige Probleme einfach lösbar macht.

Die Ziele der Komplexitätstheorie liegen also einerseits in der Klassifikation von Problemen bzgl. der nötigen Ressourcen verschiedenen Typs zu ihrer Lösung, und andererseits in der Untersuchung der strukturellen Merkmale des Begriffs Komplexität. Die größte Herausforderung besteht darin, die NP≠P-Hypothese zu beweisen.

Literatur

[1] Garey, M.R.; Johnson, D.S.: Computers and Intractability – A Guide to the Theory of NP-Completeness. W.H. Freemen, San Francisco, 1979.

[2] Reischuk, K.R.: Einführung in die Komplexitätstheorie. Teubner-Verlag Stuttgart, 1990.

[3] Wegener, I.: Theoretische Informatik – eine algorithmenorientierte Einführung. Teubner-Verlag Stuttgart, 1993.