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 Komplexitätstheorie unterscheidet sich 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 Instanz und einer konkret für sie gewählten Repräsentation. Eine Instanz des Traveling-Salesman-Problems könnte z.B. das Finden einer möglichst optimalen Route durch die Landeshauptstädte Deutschlands sein. Eine mögliche Modellierung und Repräsentation dieses Problems bestünde in der Definition eines geeigneten Graphen in Form einer Adjazenzmatrix mit den darauf auszuführenden Berechnungen. Die Aussagen der Komplexitätstheorie beziehen sich jedoch meist auf beliebige Instanzen und auf möglichst abstrakte Repräsentationen des Problems.

Entscheidungsprobleme werden bevorzugt

Darüber hinaus verzichtet man in der Komplexitätstheorie oft 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 Motivation 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 Berechnung 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 Instanzen 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

Die Betrachtung von best, worst und average case bezieht sich auf zwar beliebige, aber feste Eingabelängen. Auch wenn die Betrachtung konkreter Eingabelängen in der Praxis von großem Interesse sein kann, ist diese Sichtweise für die Komplexitätstheorie meist nicht abstrakt genug. Welche Eingabelänge als groß oder praktisch relevant gilt, kann sich aufgrund technischer Entwicklungen sehr schnell ändern. Es ist daher gerechtfertigt, das Verhalten von Algorithmen in Bezug auf ein Problem gänzlich unabhängig von konkreten Eingabelängen zu untersuchen. Man betrachtet hierzu das Verhalten der Algorithmen für immer größer werdende, potentiell unendlich große Eingabelängen und spricht auch vom asymptotischen Verhalten des jeweiligen Algorithmus.

Bei dieser Untersuchung des asymptotischen Ressourcenverbrauchs spielen untere und obere Schranken eine zentrale Rolle. Man möchte also wissen, welche Ressourcen für die Entscheidung eines Problems mindestens und höchstens benötigt werden. 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 entscheiden 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 entscheiden. Dies erfordert eine grundlegend andere, abstraktere 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:

Zeitkomplexität und Platzkomplexität
deterministisch und nichtdeterministisch

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