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.

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 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 zum Beispiel linear, polynomiell, 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 in 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 garnicht 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.

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 machen, 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 beiden 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²)
polynomiell	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 Zeitklassen.
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.

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)

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