Komplexitätstheorie
Hier wird die Komplexitätstheorie im Sinne der Informatik abgehandelt. Zur Komplexitätstheorie im kybernetischen Sinne finden Sie mehr unter komplexe Systeme
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen, sowie der Güte der sie lösenden Algorithmen. Die Untersuchung der Komplexität bezieht sich dabei auf den Ressourcenverbrauch der Algorithmen, meist auf die Rechenzeit oder den Speicherplatzbedarf). Die intellektuelle Komplexität von Problemen aus der Sicht des Menschen, etwa im Sinne einer schweren Verständlichkeit von Problemen, ist hingegen nicht Gegenstand der Komplexitätstheorie. Darüber hinaus unterscheidet sich dieser Forschungsbereich von der Berechenbarkeitstheorie, die sich mit der Frage beschäftigt, welche Probleme prinzipell algorithmisch gelöst werden können.
Probleme aus Sicht der Komplexitätstheorie
Abstraktion von Instanzen und Repräsentationen
Den zentralen Gegenstand der Komplexitätstheorie bilden Probleme. Man unterscheidet dabei zunächst Probleme von ihren Instanzen und von ihrer Repräsentation. So ist z.B. das Traveling-Salesman-Problem ein vielzitiertes Problem, das darin besteht von einem definierten Ort aus mit möglichst geringen Kosten eine Reihe weiterer Orte zu besuchen und schließlich wieder zum Ausgangsort zurückzukehren. Die Formulierung dieses Problems aus Sicht der Komplexitätstheorie ist völlig unabhängig von irgendeiner gewählten Repräsentation (ein Graph als Adjazenzmatrix, Adjazenzliste oder anders) und ebenso von einer konkreten Instanz des Problems (z.B. das Finden einer möglichst optimalen Route durch die Landeshauptstädte Deutschlands). Die Aussagen der Komplexitätstheorie beziehen sich auf beliebige Repräsentationen und Instanzen des Problems.
Entscheidungsprobleme werden bevorzugt
Darüber hinaus verzichtet man in der Komplexitätstheorie meist darauf, Problemlösungen zu generieren, sondern begnügt sich mit der Antwort, ob ein Problem mit einem definierten Ressourcenaufwand lösbar ist oder nicht. So formulierte Probleme bezeichnet man auch als Entscheidungsprobleme. Die Ursache dieser Vereinfachung besteht darin, dass man sich im Rahmen der Komplexitätsanalyse eine Behandlung der Ausgabe einer Problemlösung ersparen möchte - zumal diese ohnehin meist von einer konkreten Repräsentation abhängig ist.
Problemgrößen
Hat man ein Problem mathematisch-formal definiert (z.B. das Traveling-Salesman-Problem in Form eines Graphen), so möchte man nun Aussagen darüber treffen, wie sich ein Algorithmus bei der Lösung dieses Problems verhält. Potentiell wären viele verschiedene Aspekte des Problems zu betrachten. Normalerweise existiert jedoch eine Größe, die das Verhalten des Algorithmus im Hinblick auf den Ressourcenverbrauch maßgeblich beeinflusst. Diese Größe bezeichnet man als Problemgröße oder Eingabelänge. Man untersucht nun das Verhalten des Algorithmus im Hinblick auf unterschiedliche Problemgrößen. So ist beispielsweise das Traveling-Salesman-Problem für die Eingabelänge 2 trivial, da es hier überhaupt nur eine mögliche Lösung gibt und diese folglich auch optimal sein muss. Es ist jedoch zu erwarten, dass der Algorithmus für größere Eingaben mehr Arbeit leisten muss. Die Komplexitätstheorie interessiert sich nun für die Frage: Wieviel Mehrarbeit ist für wachsende Problemgrößen notwendig? Steigt der Aufwand linear? Oder Quadratisch? Oder steigt er gar ab einer gewissen Problemgröße nur noch sehr gering an?
Best, worst und average case
Auch innerhalb einer Problemgröße lassen sich verschiedene Verhaltensweisen von Algorithmen beobachten. So hat das Traveling-Salesman-Problem für die 16 deutschen Landeshauptstädte dieselbe Problemgröße n=16 wie das Finden einer Route durch 16 europäische Hauptstädte. Es ist keineswegs zu erwarten, dass ein Algorithmus unter den unterschiedlichen Bedingungen (selbst bei gleicher Problemgröße) jeweils gleich gut arbeitet. Da es jedoch praktisch unendlich viele Variationen für ein Problem geben kann, gruppiert man diese zumeist grob in drei Gruppen: best case, worst case und average case. Diese stehen für die Fragen:
- Best case: Wie arbeitet der Algorithmus (in Bezug auf die in Frage stehende Ressource) im besten Fall?
- Worst case: Wie arbeitet der Algorithmus im schlimmsten Fall?
- Average case: Wie arbeitet der Algorithmus durchschnittlich (wobei die zugrundegelegte Verteilung für die Berechnung eines Durchschnitts nicht immer offensichtlich ist)?
Untere und obere Schranken
Bei der Untersuchung des Ressourcenverbrauchs von Algorithmen spielen untere und obere Schranken eine zentrale Rolle. Für die Komplexitätstheorie sind vor allem die unteren Schranken von Interesse: Man möchte zeigen, dass ein bestimmter Problemtyp mindestens einen bestimmten Ressourcenverbrauch beansprucht und es folglich keinen Algorithmus geben kann, der das Problem mit geringeren Ressourcen lösen kann. Im Gegensatz zum Nachweis von oberen Schranken, der in der Regel durch die Analyse konkreter Algorithmen erfolgen kann, muss sich also eine Untersuchung der unteren Schranken auch auf Algorithmen beziehen, die noch garnicht gefunden wurden, also auf die Menge aller, auch der noch unbekannten Algorithmen, die ein bestimmtes Problem lösen. Dies erfordert eine grundlegend andere, sehr abstrakte Herangehensweise als die Analyse von bereits bekannten Algorithmen und gilt daher als schwer zugänglicher Teilbereich der Informatik.
Verwendete Rechnermodelle
Als Rechnermodelltypen werden dabei hauptsächlich
- deterministische Maschinen
- randomisierte Maschinen (die durch randomisierte Algorithmen simuliert werden),
- nichtdeterministische Maschinen,
- randomisierte nichtdeterministische Maschinen und
- quantenmechanische Maschinen
untersucht. In der Regel werden diese als
- Registermaschinen oder
- spezielle Turingmaschinen
realisiert.
Bildung von Komplexitätsklassen
Ein wesentliches Resultat der Komplexitätstheorie ist die Bildung von Komplexitätsklassen und Aussagen über deren wechselseitige Beziehungen. Die Einteilung von algorithmischen Problemen in Komplexitätsklassen erfolgt im Wesentlichen auf zwei Achsen:
Anwendungsbereiche
Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie. Auch in der Informationstheorie findet sie Andwendung, wobei dort die Komplexität einer Nachricht als Maß für ihren Informationsgehalt bestimmt werden soll: siehe auch algorithmischer Informationsgehalt und algorithmische Tiefe.
Siehe auch
P/NP-Problem, NP, NC