Komplexitätstheorie

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. Eines der wichtigsten Forschungsziele der Komplexitätstheorie besteht demgegenüber darin, die Menge der effizient lösbaren Probleme einzugrenzen.

Einordnung in die Theoretische Informatik

Datei:Theoretische-informatik.png

Die Komplexitätstheorie in der Theoretischen Informatik

Die Komplexitätstheorie gilt neben der Berechenbarkeitstheorie und der Automatentheorie als einer der drei Hauptbereiche der theoretischen Informatik. Zu ihren wesentlichen Forschungszielen gehört die Klassifizierung von Problemen im Hinblick auf den zu ihrer Lösung notwendigen Aufwand. Eine besondere Rolle spielt dabei die Abgrenzung der praktisch effizient lösbaren Probleme. Die Komplexitätstheorie grenzt daher diejenigen Probleme ein, in denen andere Disziplinen der Informatik überhaupt sinnvollerweise nach effizienten Lösungen suchen sollten.

Neben den reinen Forschungsergebnissen bereichert auch das Methodenarsenal der komplexitätstheoretischen Forschung zahlreiche angrenzende Gebiete. So führt etwa ihre enge Verzahnung mit der Automatentheorie zu neuen Maschinenmodellen und einem umfassenderen Verständnis der Arbeitsweise von Automaten. Die häufig konstruktive Beweisführung findet auch im Rahmen des Entwurfs und der Analyse von Algorithmen und Datenstrukturen Anwendung.

Probleme aus Sicht der Komplexitätstheorie

Probleme als formale Sprachen

Den zentralen Gegenstand der Komplexitätstheorie bilden Probleme. Ein Problem wird dabei als formale Sprache verstanden, und die Berechnung besteht darin, für ein gegebenes Wort zu entscheiden, ob es zu der Sprache gehört oder nicht. Diese Vorgehensweise erklärt sich anhand folgender Überlegung: Jede Maschine ist zu nichts anderem in der Lage als zur Manipulation von Symbolen. Symbolfolgen werden als Worte, Wortmengen werden als Sprachen betrachtet. Probleminstanzen müssen der Maschine also in Form konkreter Worte zur Berechnung übergeben werden. Wie im untenstehenden Abschnitt über Entscheidungsprobleme noch ausgeführt wird, einigt man sich in der Regel darauf, dass die Maschine für ein gegebenes Wort nur meldet, ob das damit beschriebene Problem lösbar ist oder nicht. Man sagt dann: Die Maschine akzeptiert das Wort (sie gibt z.B. eine 1 aus, um das Akzeptieren der Außenwelt mitzuteilen). Übertragen in die Problemwelt bedeutet dies also, dass das Problem eine Lösung hat. Aus der Sicht der Maschine stellen sich Probleme demnach als Sprachen dar. Die für eine Maschine lösbaren Probleme werden gerade durch die Worte repräsentiert, welche die Maschine akzeptiert.

Probleminstanzen

Im vorhergehenden Abschnitt war bereits davon die Rede, dass der Maschine Probleminstanzen in Form konkreter Worte übergeben werden. Eine Probleminstanz ist nicht mit dem Problem selbst zu verwechseln. Ein Problem stellt in der Komplexitätstheorie eine abstrakte Fragestellung dar: Man möchte zu Aussagen für beliebige Instanzen von Problemen gelangen. Eine Instanz des Traveling-Salesman-Problems könnte z.B. das Finden einer möglichst optimalen Route durch die Landeshauptstädte Deutschlands sein. Eine Aussage über diese Route hat jedoch nur begrenzten Wert für andere Problemstellungen, die mit der Optimierung einer Route zu tun haben. In der Komplexitätstheorie interessiert man sich daher für Aussagen, die unabhängig von konkreten Instanzen sind.

Problemrepräsentationen

Das oben über Probleminstanzen Gesagte trifft auch auf die Repräsentation von Problemen zu. Auch wenn letztlich für Beweisführungen eine konkrete Repräsentation definiert werden muss, so versucht man die Betrachtung unabhängig von Repräsentationen zu halten. Dies kann etwa erreicht werden, indem man sicherstellt, dass die gewählte Repräsentation bei Bedarf ohne allzu großen Aufwand in eine andere Repräsentation transformiert werden kann, ohne dass sich hierdurch die Berechnungsaufwände insgesamt signifikant verändern. Um dies zu ermöglichen, ist u.a. die Auswahl eines geeigneten universellen Maschinenmodells von Bedeutung.

Entscheidungsprobleme

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 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 für die Frage: Wieviel Mehrarbeit ist für wachsende Problemgrößen notwendig? Steigt der Aufwand zum Beispiel linear, polynomial, exponentiell oder gar überexponentiell?

Best, worst und average case für Problemgrößen

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 für Probleme

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.

Maschinenmodelle in der Komplexitätstheorie

Kostenfunktionen

Zur Analyse des Ressourcenverbrauchs von Algorithmen sind geeignete Kostenfunktionen zu definieren, welche eine Zuordnung der Arbeitsschritte des Algorithmus zu den verbrauchten Ressourcen ermöglichen. Um dies tun zu können, muss zunächst festgelegt werden, welche Art von Arbeitsschritt einem Algorithmus überhaupt erlaubt ist. Diese Festlegung erfolgt in der Komplexitätstheorie über abstrakte Maschinenmodelle - würde man auf reale Rechnermodelle zurückgreifen, so wären die gewonnenen Erkenntnisse bereits in wenigen Jahren überholt. Der Arbeitsschritt eines Algorithmus erfolgt in Form einer Befehlsausführung auf einer bestimmten Maschine. Die Befehle, die eine Maschine ausführen kann, sind dabei durch das jeweilige Modell streng limitiert. Darüber hinaus unterscheiden sich verschiedene Modelle etwa in der Handhabung des Speichers und in ihren Fähigkeiten zur parallelen Verarbeitung, d.h. der gleichzeitigen Ausführung mehrerer Befehle. Die Definition der Kostenfunktion erfolgt nun durch eine Zuordnung von Kostenwerten zu den jeweils erlaubten Befehlen.

Kostenmaße

Häufig wird von unterschiedlichen Kosten für unterschiedliche Befehle abstrahiert und als Kostenwert für eine Befehlsausführung immer 1 gesetzt. Sind auf einer Maschine beispielsweise Addition und Multiplikation die erlaubten Operationen, so zählt man für jede Addition und jede Multiplikation, die im Laufe des Algorithmus berechnet werden müssen, den Kostenwert von 1 hinzu. Man spricht dann auch von einem uniformen Kostenmaß. Ein solches Vorgehen ist dann gerechtfertigt, wenn sich die erlaubten Operationen nicht gravierend unterscheiden und wenn der Wertebereich, auf dem die Operationen arbeiten, nur eingeschränkt groß ist. Dies wird schon für eine einfache Operation wie die Multiplikation klar: Das Produkt zweier einstelliger Dezimalziffern dürfte sich ungleich schneller errechnen lassen als das Produkt zweier hundertstelliger Dezimalziffern. Bei einem uniformen Kostenmaß würde beide Operationen dennoch mit einem Kostenwert von 1 veranschlagt. Sollten sich die möglichen Operanden im Laufe eines Algorithmus tatsächlich so gravierend unterscheiden, so muss ein realistischeres Kostenmaß gewählt werden. Häufig wählt man dann das logarithmische Kostenmaß. Der Bezug auf den Logarithmus ergibt sich daraus, dass sich eine n-stellige Dezimalzahl durch log n Binärziffern darstellen lässt. Man wählt zur Repräsentation der Operanden Binärziffern aus und definiert die erlaubten boolschen Operationen. Sollte das jeweilige Maschinenmodell Adressen verwenden, so werden auch diese binär codiert. Auf diese Weise werden die Kosten über die Länge der Binärdarstellung logarithmisch gewichtet. Andere Kostenmaße sind möglich, werden jedoch nur selten eingesetzt.

Maschinenmodelle und Probleme

Man unterscheidet zwei Typen von Maschinenmodellen: deterministische Maschinen und nichtdeterministische Maschinen. Von den meisten Maschinenmodellen existiert sowohl eine deterministische als auch eine nichtdeterministische Version. Nichtdeterministische Maschinen verfügen zwar über unrealistische Fähigkeiten (sie "erraten" einen richtigen Pfad in einem Berechnungsbaum), lassen sich jedoch im allgemeinen erheblich leichter zu einem gegebenen Problem konstruieren. Da eine Transformation von nichtdeterministischen in deterministische Maschinen immer relativ einfach möglich ist, konstruiert man daher zunächst eine nichtdeterministische Maschinenversion und transformiert diese später in eine deterministische.

Daraus geht eine wichtige Beweistechnik der Komplexitätstheorie hervor: Lässt sich zu einem gegebenen Problem ein bestimmter Maschinentyp konstruieren, auf dem das Problem mit bestimmten Kosten entschieden werden kann, so kann damit bereits die Komplexität des Problems eingeschätzt werden. Tatsächlich werden sogar die unterschiedlichen Maschinenmodelle bei der Definition von Komplexitätsklassen zugrundegelegt. Dies entspricht einer Abstraktion von einem konkreten Algorithmus: Wenn ein Problem auf Maschine M entscheidbar ist (wobei ein entsprechender Algorithmus evtl. noch gar nicht bekannt ist), so lässt es sich unmittelbar einer bestimmten Komplexitätsklasse zuordnen, nämlich derjenigen, die von M definiert wird. Dieses Verhältnis zwischen Problemen und Maschinenmodellen ermöglicht Beweisführungen ohne die umständliche Analyse von Algorithmen.

Häufig eingesetzte Maschinenmodelle

Besonders häufig eingesetzte Modelle sind:

Zur Untersuchung parallelisierbarer Probleme können darüber hinaus auch parallelisierte Versionen dieser Maschinen zum Einsatz kommen, insbesondere die parallele Registermaschine.

Die erweiterte Church'sche These

Für die Verwendung von Maschinenmodellen in der Komplexitätstheorie ist eine Erweiterung der These von Church von Bedeutung, die auch als erweiterte Church'sche These bezeichnet wird. Sie besagt, dass alle universellen Maschinenmodelle in Bezug auf die Rechenzeit bis auf polynomielle Faktoren gleich mächtig sind. Dies ermöglicht dem Komplexitätstheoretiker eine relativ freie Wahl des Maschinenmodells im Hinblick auf das jeweilige Untersuchungsziel.

Modellmodifikationen für Speicherplatzanalysen

Zur Untersuchung des Mindestspeicherbedarfs, der für die Lösung von Problemen benötigt wird, nimmt man häufig die folgenden Modifikationen des verwendeten Maschinenmodells (in der Regel eine Turingmaschine) vor:

Der Eingabespeicher darf nur gelesen werden.
Auf die Ausgabe darf nur geschrieben werden. Der Schreibkopf wird nur nach Schreibvorgängen und immer in dieselbe Richtung bewegt (falls das Maschinenmodell eine solche Bewegung vorsieht).

Für die Untersuchung des Speicherbedarfs dürfen dann Ein- und Ausgabe der Maschine unberücksichtigt bleiben. Die Motivation für diese Änderungen ist die folgende: Würde z.B. der Eingabespeicher in die Speicherplatzanalyse einbezogen, so könnte kein Problem in weniger als O(n) Platzbedarf gelöst werden, denn das Eingabewort hat ja immer genau die Länge und damit den Speicherbedarf n. Indem man die Eingabe nur lesbar macht, verhindert man, dass sie für Zwischenrechnungen verwendet werden kann. Man kann dann die Eingabe bei der Berechnung des Platzbedarfs vernachlässigen. Eine ähnliche Argumentation führt zu der Einschränkung der Ausgabe. Durch die zusätzliche Einschränkung einer möglichen Kopfbewegung wird verhindert, dass die Kopfposition verwendet wird, um sich Information zu "merken". Insgesamt stellen all diese Einschränkungen sicher, dass Ein- und Ausgabe bei der Speicherplatzanalyse nicht berücksichtigt werden müssen.

Die vorgenommenen Modifikationen beeinflussen das Zeitverhalten der Maschine übrigens nur um einen konstanten Faktor und sind damit vernachlässigbar.

Verwendung und Rechtfertigung der O-Notation

Bei der Untersuchung von Größenordnungen für Aufwände wird in der Komplexitätstheorie ausgiebig von der O-Notation Gebrauch gemacht. Dabei werden lineare Faktoren und Konstanten aus der Betrachtung ausgeblendet. Diese Vorgehensweise mag zunächst überraschen, wäre doch für den Praktiker häufig bereits eine Halbierung der Aufwände von hoher Bedeutung.

Der Standpunkt der Komplexitätstheorie lässt sich theoretisch mit einer Technik rechtfertigen, die man als lineares Beschleunigen oder auch Speedup-Theorem bezeichnet. (Wir beschränken uns hier auf das Zeitverhalten. Analoge Beweise kann man auch für den Speicherbedarf oder andere Ressourcen führen.) Das Speedup-Theorem besagt vereinfachend, dass sich zu jeder Turingmaschine, die ein Problem in O(f) Zeit berechnet, eine neue Turingmaschine konstruieren lässt, die das Problem in O(f') Zeit mit f' = ε·f (ε>0) berechnet. Das bedeutet nichts anderes, als dass sich jede Turingmaschine, die ein bestimmtes Problem löst, um einen beliebigen linearen Faktor beschleunigen lässt. Der Preis für diese Beschleunigung besteht in einer stark vergrößerten Zustandsmenge der verwendeten Turingmaschine (letztlich also "Hardware").

Die Beschleunigung wird unabhängig von der Problemgröße erreicht. Es würde daher keinen Sinn ergeben, lineare Faktoren bei der Betrachtung von Problemen zu berücksichtigen - solche Faktoren ließen sich durch eine geeignete Maschinendefinition ohnehin beseitigen. Umgekehrt wüsste man garnicht, ob sich der jeweils angegebene Faktor nun durch das Problem selbst oder durch die jeweils gewählte Maschinendefinition ergeben hat. Die Vernachlässigung linearer Faktoren, die sich in der O-Notation ausdrückt, hat daher nicht nur praktische Gründe, sie vermeidet auch Verfälschungen im Rahmen komplexitätstheoretischer Betrachtungen.

Bildung von Komplexitätsklassen

Ein wesentliches Resultat der Komplexitätstheorie ist die Bildung von Komplexitätsklassen und Aussagen über deren wechselseitige Beziehungen.

Einflussgrößen bei der Bildung von Komplexitätsklassen

Eine Reihe von Faktoren nehmen auf die Bildung von Komplexitätsklassen Einfluss. Die wichtigsten sind die folgenden:

Das zugrundeliegende Berechnungsmodell (Turingmaschine, Registermaschine usw.).
Der verwendete Berechnungsmodus (deterministisch, nichtdeterministisch, probabilistisch usw.).
Die betrachtete Berechnungsressource (Zeit, Platz, Prozessoren usw.).
Das angenommene Kostenmaß (uniform, logarithmisch).
Die eingesetzte Schrankenfunktion.

Anforderungen an Schrankenfunktionen

Zur Angabe oder Definition von Komplexitätsklassen verwendet man Schrankenfunktionen. Schreibt man beispielsweise DTIME(f), so meint man damit die Klasse aller Probleme, die auf einer deterministischen Turingmaschine in der Zeit O(f) entschieden werden können. f ist dabei eine Schrankenfunktion. Um als Schrankenfunktion für komplexitätstheoretische Analysen eingesetzt werden zu können, sollte die Funktion mindestens die folgenden Anforderungen erfüllen:

f: N -> N (Schrittzahl, Speicher usw. werden als natürliche Zahlen berechnet).
f(n+1) ≥ f(n) (monotones Wachstum).
Die Funktion f muss selbst in Zeit O(f) und mit Raum O(f) berechenbar sein.

Eine Funktion, die diesen Anforderungen genügt, bezeichnet man auch als echte Komplexitätsfunktion. Der Sinn der Anforderungen ist zum Teil technischer Natur. Die Schrankenfunktion kann selbst auf konstruktive Art (z.B. als Turingmaschine) in Beweise einfließen und sollte sich daher für diese Zwecke "gutartig" verhalten. An dieser Stelle soll nur bewusst gemacht werden, dass bei der Wahl der Schrankenfunktion eine gewisse Vorsicht walten muss, um nicht zu widersprüchlichen Ergebnissen zu gelangen.

Die meisten "natürlichen" Funktionen entsprechen den oben genannten Einschränkungen, so etwa die konstante Funktion, die Logarithmusfunktion, die Wurzelfunktion, Polynome, die Exponentialfunktion sowie alle Kombinationen dieser Funktionen. Es folgt eine Übersicht der wichtigsten Schrankenfunktionen mit der jeweils üblichen Sprechweise. Die Angabe erfolgt wie üblich in O-Notation.

Die wichtigsten Schrankenfunktionen

konstant	O(1)
logarithmisch	O(log n)
polylogarithmisch	O(log^k n) für k ≥ 1
linear	O(n)
n-log-n	O(n log n)
quadratisch	O(n²)
polynomial	O(n^k) für k ≥ 1
exponentiell	O(dⁿ) für d ≥ 1

Hierarchiesätze

Für die gebildeten Klassen möchte man möglichst beweisen, dass durch zusätzlich bereitgestellte Ressourcen tatsächlich mehr Probleme gelöst werden können. Diese Beweise bezeichnet man als Hierarchiesätze, da sie auf den Klassen der jeweiligen Ressource eine Hierarchie induzieren. Es gibt also Klassen, die in eine echte Teilmengenbeziehung gesetzt werden können. Wenn man solche echten Teilmengenbeziehungen ermittelt hat, lassen sich auch Aussagen darüber treffen, wie groß die Erhöhung einer Ressource sein muss, um damit eine größere Zahl von Problemen berechnen zu können. Von besonderem Interesse sind dabei wiederum die Ressourcen Zeit und Raum. Die induzierten Hierarchien bezeichnet man auch als Zeithierarchie und Raumhierarchie.

Die Hierarchiesätze bilden letztlich das Fundament für die Separierung von Komplexitätsklassen. Sie waren daher auch eines der frühesten Ergebnisse der Komplexitätstheorie. Ohne die Hierarchiesätze müsste für die Beziehungen der unterschiedlichen Klassen statt einer ⊂-Hierarchie eine ⊆-Hierarchie angenommen werden. Es bliebe dann zu befürchten, dass die gesamte Hierarchie zu einer einzigen Klasse kollabiert. Tatsächlich muss ergänzt werden, dass alle Hierarchiesätze auf diversen Voraussetzungen beruhen. Eine dieser Voraussetzungen ist etwa, dass die oben genannten Anforderungen an echte Komplexitätsfunktionen erfüllt werden. Ohne die Einhaltung dieser Anforderungen bricht tatsächlich die gesamte Klassenhierarchie in sich zusammen.

Exkurs: Derartige Probleme gibt es beispielsweise im Bereich der probabilistischen Komplexitätsklassen. Schränkt man hier - wie für praktisch verwendbare probabilistische Algorithmen erforderlich - die Fehlerwahrscheinlichkeit ein, so resultiert daraus u.a., dass die Komplexitätsklassen nicht mehr aufzählbar sind. Dies ist aber für alle Separationsverfahren eine Voraussetzung. Als Ergebnis lassen sich Polynomzeitalgorithmen plötzlich durch Linearzeitalgorithmen ersetzen. Das Beispiel zeigt, wie sensibel das Geflecht aus Voraussetzungen und den abgeleiteten Sätzen insgesamt ist.

Zeithierarchiesatz

Der Zeithierarchiesatz besagt:

DTIME(f(n))\subset DTIME(f(n)\cdot log^{2}(f(n)))

Dies bedeutet also, dass man die Zeitressource um einen Faktor $log^{2}(f(n))$ erhöhen muss, um auf einer deterministischen Turingmaschine mehr Probleme lösen zu können. Eine ähnliche Beziehung lässt sich für nichtdeterministische Turingmaschinen finden.

Raumhierarchiesatz

Der Raumhierarchiesatz besagt:

DSPACE(f(n))\subset DSPACE(f(n)\cdot log(f(n)))

Die Aussage ist analog zum Zeithierarchiesatz. Man erkennt jedoch, dass im Vergleich zur Zeit bereits eine geringere Steigerung des Raumes ausreicht (Faktor $log(f(n))$ im Vergleich zu $log^{2}(f(n))$ ), um eine größere Klasse zu bilden. Dies entspricht auch einer intuitiven Erwartung, verhält sich doch der Raum insgesamt aufgrund seiner Wiederverwendbarkeit (alte Zwischenergebnisse können überschrieben werden) gutmütiger.

Wofür die Hierarchiesätze nicht gelten

Die Hierarchiesätze beziehen sich ausschließlich auf den jeweils gleichen Berechnungsmodus und eine einzelne Ressource, also z.B. auf die Ressource Zeit auf einem deterministischen Maschinenmodell. Es wird jedoch keine Aussage darüber getroffen, wie sich etwa Raum- und Zeitklassen zueinander verhalten oder in welchem Verhältnis deterministische oder nichtdeterministische Klassen zueinander stehen. Dennoch gibt es derartige Zusammenhänge. Sie werden in den Abschnitten Beziehungen zwischen Raum- und Zeitklassen und Beziehungen zwischen deterministischen und nichtdeterministischen Klassen behandelt.

Wichtige Zeitklassen

DTIME(f): Allgemeine Schreibweise für deterministische Zeitklassen.
P: Deterministisch in Polynomialzeit entscheidbare Sprachen.
EXPTIME: Deterministisch in Exponentialzeit entscheidbare Sprachen.
NTIME(f): Allgemeine Schreibweise für nichtdeterministische Zeitklassen.
NP: Nichtdeterministisch in Polynomialzeit entscheidbare Sprachen.
NEXPTIME: Nichtdeterministisch in Exponentialzeit entscheidbare Sprachen.
NC: Parallel in polylogarithmischer Zeit berechenbare Funktionen.

Wichtige Raumklassen

DSPACE(f): Allgemeine Schreibweise für deterministische Raumklassen.
L: Deterministisch mit logarithmischem Raum entscheidbare Sprachen.
PSPACE: Deterministisch in mit polynomialem Raum entscheidbare Sprachen.
NSPACE(f): Allgemeine Schreibweise für nichtdeterministische Raumklassen.
NL: Nichtdeterministisch mit logarithmischem Raum entscheidbare Sprachen.

Komplementbildungen

Für jede Komplexitätsklasse lässt sich das Komplement bilden, indem man die Menge der nicht erkannten Worte als Menge der erkannten Worte definiert und umgekehrt. Der neu gebildeten Komplementklasse stellt man das Präfix co vor. Heißt also die Ausgangsklasse K, so heißt ihr Komplement coK. Für deterministische Maschinen gilt häufig K = coK, da in der Übergangsfunktion einfach nur die Übergänge zu akzeptierenden Zuständen durch Übergänge zu verwerfenden Zuständen ausgetauscht werden müssen und umgekehrt. Für andere Berechnungsmodi gilt dies jedoch nicht, da hier die Akzeptierung anders definiert ist. Beispielsweise ist bislang unbekannt, ob NP = coNP gilt. P = coP ist jedoch bewiesen.

Das P/NP-Problem und seine Bedeutung

Eines der wichtigsten und nach wie vor ungelösten Probleme der Komplexitätstheorie ist das P/NP-Problem. Ist die Klasse P gleich der Klasse NP? Diese Frage kann als die zentrale Forschungsmotivation der Komplexitätstheorie angesehen werden, und eine Vielzahl der komplexitätstheoretischen Ergebnisse wurde erzielt, um der Lösung des P/NP-Problems näher zu kommen.

Die Klasse P: Praktisch lösbare Probleme

Die Tragweite des P/NP-Problems resultiert aus der Erfahrung, dass die Probleme der Klasse P in der Regel praktisch lösbar sind: Es existieren Algorithmen, um Lösungen für diese Probleme effizient oder doch mit vertretbarem zeitlichen Aufwand zu berechnen. Der zeitliche Aufwand zur Problemlösung wächst für die Probleme der Klasse P maximal polynomial. Meist lassen sich sogar Algorithmen finden, deren Zeitfunktionen Polynome niedrigen Grades sind. Da das gewählte Maschinenmodell dieser Zeitklasse deterministisch und damit tatsächlich realisierbar ist, bilden die Probleme der Klasse P gerade die Grenze des algorithmisch sinnvollerweise Machbaren.

Die Klasse NP: Praktisch (vermutlich) nicht lösbare Probleme

Im Gegensatz zu den Problemen in P basieren die Algorithmen zur Lösung der Probleme in NP auf einem nichtdeterministischen Maschinenmodell. Für solche Maschinen wird eine unbeschränkte Parallelisierbarkeit der sich verzweigenden Berechnungspfade angenommen, die technisch nicht realisiert werden kann. Zwar arbeiten auch die Algorithmen zur Lösung der Probleme in NP in polynomialer Zeit, aber eben auf der Basis eines unrealistischen Maschinenmodells. Die Probleme in NP gelten daher für praktische Zwecke als nicht lösbar: Der Aufwand zur ihrer Berechnung steigt auf einer deterministischen Maschine mutmaßlich mit wachsender Problemgröße mehr als polynomial an. Dies wäre nicht weiter tragisch, wenn nicht so viele Probleme von größter Bedeutung zu NP gehören würden. Tatsächlich finden sich jedoch in NP Probleme aus fast allen Bereichen der Informatik, deren effiziente Lösung enorm wichtig wäre.

Der Fall P = NP

Würde das P/NP-Problem im Sinne von P = NP gelöst, so hätte dies einen schlagartigen Zuwachs an Problemlösekraft in der gesamten Informatik zur Folge, wie er auch durch noch so große Fortschritte in der Hardware-Entwicklung nicht erreicht werden kann. Ein zunächst nur theoretischer Beweis würde auf Grund des konstruktiven Charakters der Komplexitätstheorie auch eine baldige Realisierung effizienter Algorithmen auf realen Rechensystemen ermöglichen.

Der Fall P ≠ NP

Würde das P/NP-Problem im Sinne von P ≠ NP gelöst, so wäre damit klar, dass weitere Bemühungen, effiziente Lösungen für Probleme der Klasse NP zu finden, sinnlos wären. Man kann sich leicht vorstellen, dass auf Grund der hohen Bedeutung der Probleme in NP die Bemühungen um eine effiziente Lösung erst dann eingestellt werden, wenn diese nachgewiesenermaßen unmöglich ist. Bis zu diesem Zeitpunkt wird noch viel private und öffentliche Forschungsenergie aufgewandt werden. Es wird heute allgemein angenommen, dass P ≠ NP gilt, doch ein Beweis ist noch nicht gelungen.

Konsequenzen für die Komplexitätstheorie

Zu den wichtigsten Forschungszielen der Komplexitätstheorie gehört die Abgrenzung des praktisch Machbaren und damit des Betätigungsfeldes der Informatik schlechthin. Die vorherigen Abschnitte haben die Wichtigkeit dieser Grenzziehung verdeutlicht. 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 seit über dreißig Jahren andauernden Bemühungen, das P/NP-Problem zu lösen, gewähren darüber hinaus dem praktischen Informatiker ein großes Maß an Sicherheit, dass isolierte Bemühungen zur effizienten Lösung von Problemen aus NP mehr oder weniger sinnlos sind. P ≠ NP ist nicht bewiesen, darf aber in Anbetracht der geleisteten Aufwände in der Komplexitätstheorie vorläufig angenommen werden. Die praktische Informatik konzentriert sich daher bei der Lösung für Probleme aus NP auf Näherungslösungen oder die Abwandlung der ursprünglichen Probleme. So kann sich beispielsweise die Problemkomplexität von Optimierungs-Algorithmen enorm verringern, wenn man keine optimale Lösung anstrebt, sondern mit einer fast optimalen Lösung zufrieden ist. Die Komplexitätstheorie liefert für diese Vorgehensweise die theoretische Rückendeckung.

Sprachen und Komplexitätsklassen

Der folgende Baum gibt einen - recht groben - Überblick über die Zusammenhänge zwischen Sprachen der Chomsky-Hierarchie und verschiedenen Komplexitätsklassen.

Entscheidungsproblem

Typ 0 (rekursiv aufzählbar)

Typ 1 (kontextsensitiv)

PSPACE-vollständig

CoNP

NP

BPP

BQP

NP-vollständig

P

NC

P-vollständig

Typ 2 (kontextfrei)

Typ 3 (regulär)

Geschichte der Komplexitätstheorie

Nachdem in den vorhergehenden Abschnitten zahlreiche Grundbegriffe und wichtige Ergebnisse der Komplexitätstheorie erläutert wurden, wir in den folgenden Abschnitten ein geschichtlicher Abriss gegeben, der die zeitliche Abfolge dieser Ergebnisse einordnen helfen soll.

Grundlagen

Vor dem eigentlichen Beginn der explizit auf die Komplexität von Algorithmen bezogenen Forschung wurden zahlreiche Grundlagen erarbeitet. Als wichtigste kann dabei die Konstruktion der Turingmaschine durch Alan Turing im Jahr 1936 angesehen werden, die sich für spätere Algorithmen-Analysen als ausgesprochen flexibles Modell erwies.

Als erste informelle komplexitätstheoretische Untersuchungen werden Ergebnisse von John Myhill (1960), Raymond Smullyan (1961) und H. Yamada (1962) angesehen, die sich mit speziellen raum- und zeitbeschränkten Problemklassen beschäftigt haben, jedoch in ihren Arbeiten noch keinen Ansatz zu einer allgemeinen Theorie entwickelten.

Beginn der komplexitätstheoretischen Forschung

Einen ersten großen Schritt in Richtung einer solchen Theorie unternehmen Juris Hartmanis und Richard Stearns in ihrer 1965 erschienenen Arbeit "On the computational complexity of algorithms". Sie geben bereits eine quantitative Definition von Zeit- und Platzkomplexität und wählen damit bereits die beiden Ressourcen aus, die bis heute als die wichtigsten angesehen werden. Dabei wählen sie die Mehrband-Turingmaschine als Grundlage und treffen damit eine sehr robuste Entscheidung, die in vielen komplexitätstheoretischen Feldern Bestand hat. Sie erarbeiten auch bereits erste Hierarchiesätze.

In den folgenden Jahren kommt es zu einer Reihe fundamentaler Ergebnisse. 1967 veröffentliche Manuel Blum das Speedup-Theorem. 1969 folgt das Union-Theorem von E. McCreight und A. Meyer. Und 1972 veröffentlicht A. Borodin das Gap-Theorem. Diese Ergebnisse lassen sich nicht nur als grundlegend für die Komplexitätstheorie ansehen, sie stellen auch ein Abtasten des noch neuen Forschungsgebietes dar, das sich zugleich noch durch möglichst "spektakuläre" Ergebnisse rechtfertigen muss. So treffen diese Theoreme z.T. zwar überraschende Aussagen, sind aber mitunter auf Annahmen gebaut, die man heute einschränken würde. Beispielsweise werden keine echten Komplexitätsfunktionen (siehe oben) vorausgesetzt.

In derselben Zeit, die etwa die ersten zehn Jahre komplexitätstheoretischer Forschung umfasst, kommt es zur Formulierung der Klasse P als der Klasse der "praktisch lösbaren" Probleme. A. Cobham zeigt, dass die Polynomialzeit robust unter der Wahl des Maschinenmodells ist (was man heute unter der erweiterten Church'schen These zusammenfasst). Darüber hinaus erweisen sich viele mathematische Funktionen als in Polynomialzeit berechenbar.

Erforschung der Klasse NP

Die Klasse NP tritt zuerst bei J. Edmonds auf den Plan, der jedoch zunächst nur eine informelle Definition gibt. Die Tatsache, dass zahlreiche wichtige Probleme in NP zu liegen scheinen, lässt diese Klasse jedoch bald als attraktives Forschungsfeld erscheinen. Der Begriff der Reduzierbarkeit und die darauf basierende NP-Vollständigkeit wird entwickelt und findet zuerst im Satz von Cook (1971) prägnanten Ausdruck: Das Erfüllbarkeitsproblem (SAT) ist NP-vollständig und damit ein schwerstes Problem in NP. Nebenbei bemerkt bezog sich die ursprüngliche Arbeit von Cook auf Tautologien (Formeln, die durch jede Belegung erfüllt werden), während der Begriff der Erfüllbarkeit nicht erwähnt wird. Da die Ergebnisse bezüglich der Tautologien jedoch relativ einfach auf die Erfüllbarkeit übertragen werden können, rechnet man sie Stephen Cook zu. Einen Teil dieser Übertragung leistet Richard Karp (1972), indem er die Technik der Reduktion ausarbeitet. Völlig unabhängig von diesen Arbeiten entwickelte Leonid Levin (1973) in der damaligen Sowjetunion eine Theorie der NP-Vollständigkeit, die im Westen für lange Zeit unbeachtet blieb.

1979 veröffentlichen Michael R. Garey und David S. Johnson ein Buch, welches 300 NP-vollständige Probleme beschreibt (Computers and intractability). Dieses Buch wurde für künftige Forscher zu einer wichtigen Referenz.

Randomisierte Komplexitätsklassen

1982 stellt Andrew Chi-Chih Yao das Konzept der Falltürfunktionen (trapdoor functions) vor. 1984 weisen schließlich Oded Goldreich, Shafi Goldwasser und Silvio Micali die Existenz von Einwegfunktionen (one way functions) nach, die eine Verallgemeinerung der Falltürfunktionen darstellen und randomisierten Komplexitätsklassen zu Grunde liegen.

Mit dieser Übersicht wurden die wesentlichen Grundsteine der Geschichte der Komplexitätstheorie gelegt. Wie in anderen Forschungsgebieten auch, fächern sich die neueren Ergebnisse in viele, teils sehr spezielle Teilbereiche auf.

Anwendungsbereiche

Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie. Auch in der Informationstheorie findet sie Anwendung, wobei dort die Komplexität einer Nachricht als Maß für ihren Informationsgehalt bestimmt werden soll: siehe auch algorithmischer Informationsgehalt und algorithmische Tiefe.

Vorlage:Navigationsleiste Komplexitätsklassen