Die Komplexitätstheorie untersucht die Mindestressourcen zur Lösung algorithmischer Probleme und beeinflusst damit, insbesondere durch die NP-Vollständigkeitstheorie, die Entwicklung der gesamten Informatik.
Allgemeines
Die Komplexitätstheorie ist, neben der Theorie formaler Sprachen und der Berechenbarkeitstheorie, ein Kerngebiet der Theoretischen Informatik, das die algorithmisch behandelbaren Probleme und deren Komplexität untersucht. Ihr Ziel ist, für wichtige Probleme nachzuweisen, dass zu ihrer Lösung bestimmte Mindestressourcen nötig sind. Als Ressourcenverbrauch wird dabei meist Rechenzeit oder Speicherplatzbedarf auf mathematisch definierten formalen Rechnermodellen gemessen. Besonders häufig eingesetzte Rechnermodelle sind Turingmaschine, Registermaschine, Kellerautomat und endlicher Automat. Das Vorgehen der Komplexitätstheorie besteht dabei in der Klassifizierung von Problemen im Hinblick auf den zu ihrer Lösung notwendigen Aufwand.
Komplexitätsklassen und Reduktionen
Eine Komplexitätsklasse ist eine Kategorie von Problemen, zusammengefasst nach einem gemeinsamen Maß der Komplexität.
Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen. Durch sie können die Berechenbarkeit oder die Komplexität von Problemen zueinander in Bezug gesetzt werden.
Ein Problem A, das mit geringem Aufwand auf ein Problem B reduziert werden kann, gehört mindestens zur Komplexitätsklasse von B. B wird dann schwerer als A genannt. Ein Problem A ist K-schwer, wenn sich alle anderen Probleme der Klasse K auf A zurückführen lassen. Liegt ein K-schweres Problem A selbst in der Klasse K, wird es K-vollständig genannt.
Durch die Reduktion werden also die vorliegenden Probleme in Komplexitätsklassen einsortiert, und es werden Aussagen über wechselseitige Beziehungen zwischen Klassen gemacht. Ein Problem ist vollständig für eine Komplexitätsklasse, wenn jedes andere Problem der Klasse darauf reduziert werden kann. Zu den wichtigsten Zeitklassen zählen die Komplexitätsklassen P und NP.
P-NP-Problem
Algorithmisch behandelbare Probleme werden auch in der Algorithmentheorie behandelt, allerdings aus anderem Blickwinkel als in der Komplexitätstheorie. Bei der Konstruktion effizienter Algorithmen wird eine obere Schranke für den Ressourcenverbrauch zur Problemlösung ermittelt. Die komplexitätstheoretische Betrachtung des Problems liefert dagegen eine untere Schranke des Ressourcenverbrauchs, der von
jedem Algorithmus zur Lösung minimal benötigt wird. Die Aussagen der Komplexitätsanalyse eines Problems gelten also für alle Algorithmen, die dieses Problem lösen. Dementsprechend müssten zum Beweis einer solchen Schranke alle Algorithmen für das Problem betrachtet werden. Da dies unmöglich ist, kann für Probleme, die als schwer angesehen werden, nicht bewiesen werden, dass sie schwierig sind. Es wird aber gezeigt, dass zahlreiche Probleme im Wesentlichen den gleichen Schwierigkeitsgrad haben. Ein effizienter Algorithmus für eins dieser Probleme impliziert die Existenz von effizienten Algorithmen für alle anderen Probleme derselben Klasse. Andersherum würde ein Nachweis, dass eines dieser Probleme nicht effizient lösbar ist, bedeuten, dass keines effizient lösbar ist. Dies begründet die zentrale Herausforderung der Komplexitätstheorie: das NP≠P-Problem. Die Frage der Äquivalenz dieser beiden Klassen ist formal äquivalent zur Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden kann, das Finden einer solchen Lösung jedoch extrem schwierig ist.
(Für die Probleme der Klasse P sind Algorithmen bekannt, die einen polynomiellen Zeitaufwandszuwachs mit wachsender Instanzgröße aufweisen. Probleme, für die kein polynomieller Algorithmus bekannt ist, werden der Klasse NP – nichtdeterministisch polynomiell – zugeordnet.)
Viele praktische Anwendungen für NP-vollständige Probleme, wie zum Beispiel das Problem des Handlungsreisenden, das Rucksackproblem oder das Problem der Färbung von Graphen, wären im Fall NP=P exakt optimal in kurzer Zeit lösbar.
Mit dem Beweis von NP≠P wären NP-Probleme endgültig als schwer lösbar klassifiziert. NP≠P entspricht derzeit der Annahme der meisten Wissenschaftler, und der Beweis wäre weniger folgenschwer als der Beweis von NP=P.
Konsequenzen und praktische Bedeutung
Zu den Forschungszielen der Komplexitätstheorie gehört die Abgrenzung des praktisch Machbaren im Bereich der Algorithmen und damit des Betätigungsfeldes der Informatik. Im Zuge der Versuche, das P-NP-Problem zu lösen, hat die Komplexitätstheorie zahlreiche Ergebnisse zu Tage gefördert und ihre Analysemethoden Zug um Zug verfeinert. Diese Ergebnisse werden insbesondere beim Entwurf und der Analyse praktisch wichtiger Algorithmen angewandt und wirken so auch unmittelbar auf die Praktische Informatik.
Die Praktische Informatik konzentriert sich daher bei der Lösung von NP-Problemen auf Näherungslösungen oder Abwandlung des Ursprungsproblems: Die Problemkomplexität von Optimierungsalgorithmen kann sich bspw. enorm verringern, wenn man keine optimale Lösung anstrebt, sondern nur eine “fast optimale”, was aus praktischer Sicht oft völlig ausreicht. Die Komplexitätstheorie liefert für diese Vorgehensweise die theoretische Rückendeckung.
Literatur
Wegener, Ingo: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. 1. Auflage. Berlin: Springer, 2003
Papadimitriou, Christos H.: Computational Complexity. Reading/Mass.: Addison-Wesley, 1995
http://de.wikipedia.org/w/index.php?title=Komplexitätsklasse (letzter Abruf am 21.08.2011)
http://de.wikipedia.org/w/index.php?title=Komplexität_(Informatik) (letzter Abruf am 21.08.2011)
