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. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf. Es werden jedoch auch speziellere Komplexitätsmaße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen untersucht.

Die Komplexitätstheorie unterscheidet sich von der Berechenbarkeitstheorie, die sich mit der Frage beschäftigt, welche Probleme prinzipiell algorithmisch gelöst werden können. Demgegenüber besteht das wichtigste Forschungsziel der Komplexitätstheorie darin, die Menge aller lösbaren Probleme zu klassifizieren. Insbesondere versucht man, die Menge der effizient lösbaren Probleme von der Menge der inhärent schwierigen Probleme abzugrenzen.

Einordnung in die Theoretische Informatik

Die Komplexitätstheorie in der Theoretischen Informatik

Die Komplexitätstheorie gilt, neben der Berechenbarkeitstheorie und der Theorie der Formalen Sprachen, 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 und motiviert so die Entwicklung von praxistauglichen Approximationsalgorithmen.

Neben dem reinen Erkenntnisgewinn 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

Entscheidungsprobleme als formale Sprachen

Entscheidungsproblem

Den zentralen Gegenstand der Komplexitätstheorie bilden Probleme. Ein Problem wird dabei oft als formale Sprache verstanden. Die Aufgabe besteht nun darin, für ein gegebenes Wort zu entscheiden, ob es zu der Sprache gehört oder nicht. Daher spricht man hier auch von Entscheidungsproblemen. Man sagt dazu: Die Berechnung akzeptiert oder verwirft das Wort.

Ein mögliches Eingabewort könnte beispielsweise ein beliebiger Graph sein. Das Problem könnte darin bestehen zu entscheiden, ob der gegebene Graph zusammenhängend ist oder nicht. Die zugehörige entschiedene Sprache wäre demnach die Menge aller zusammenhängenden Graphen.

Man könnte annehmen, dass die Einschränkung auf solche Entscheidungsfragen viele wichtige Probleme ausschließt. Das ist jedoch nicht so. So lassen sich alle im Sinne der Komplexitätstheorie relevanten Probleme auch als Entscheidungsproblem formulieren. Betrachtet man zum Beispiel das Problem der Multiplikation zweier Zahlen, so besteht die dazugehörige Sprache des Entscheidungsproblems aus allen Zahlen-Tripeln (a,b,c) für die der Zusammenhang $a \cdot b = c$ gilt. Die Entscheidung, ob ein gegebenes Tripel zu dieser Sprache gehört, entspricht dem Lösen des Problems der Multiplikation zweier Zahlen.

Berechnungsprobleme als Abbildungen

Darüber hinaus ist man in der Komplexitätstheorie manchmal daran interessiert, Problemlösungen auch wirklich zu generieren. Hier begnügt man sich nicht mit der einfachen Ja/Nein-Antwort eines Wortproblemes für formale Sprachen. Stattdessen versteht man das Problem als eine Abbildung aus einem Definitionsbereich in seinen Lösungsraum. Die Lösung des Problemes der Multiplikation zweier Zahlen in etwa würde man als das Ergebnis der Abbildung f mit $f(a,b) = a \cdot b$ verstehen. Für die Definition der meisten Komplexitätsklassen wird jedoch die Formulierung durch Entscheidungsprobleme bevorzugt.

Eine wichtige Unterkategorie der Berechnungsprobleme stellen die Optimierungsprobleme dar. Bei Optimierungsproblemen besteht der funktionale Zusammenhang aus der Forderung, dass ein Maximum bzw. Minimum zu einer gegebenen Kostenfunktion zu der Eingabe ausgegeben werden soll. Man könnte so zum Beispiel beim Problem des Handlungsreisenden nach der optimalen Route durch die Landeshauptstädte Deutschlands fragen, welche die geringste Gesamtlänge besitzt. Viele Optimierungsprobleme sind von großer praktischer Bedeutung.

Probleminstanzen

Eine Probleminstanz ist nicht mit dem Problem selbst zu verwechseln. Ein Problem stellt in der Komplexitätstheorie die abstrakte Fragestellung dar. Dem entgegen bezeichnet die Instanz eines Problems eine ganz konkrete Ausprägung, die als Eingabe für eine solche Entscheidungsfrage dienen könnte.

Eine Instanz des Problems des Handlungsreisenden könnte zum Beispiel die Frage sein, ob eine Route durch die Landeshauptstädte Deutschlands mit einer maximalen Länge von 2000 km existiert. Die Entscheidung über diese Route hat jedoch nur begrenzten Wert für andere Probleminstanzen, wie etwa eine Rundreise durch die Sehenswürdigkeiten Mailands mit gegebener Längenschranke. In der Komplexitätstheorie interessiert man sich daher für Aussagen, die unabhängig von konkreten Instanzen sind.

Problemrepräsentationen

Als formale Sprachen werden Probleme und deren Instanzen über abstrakten Alphabeten definiert. Häufig wird das binäre Alphabet mit den Symbolen 0 und 1 gewählt, da dies der Verwendung von Bits bei modernen Rechnern am nächsten kommt. Eingaben werden dann durch Alphabetsymbole kodiert. An Stelle von mathematischen Objekten wie Graphen verwendet man möglicherweise eine Bitfolge die der Adjazenzmatrix des Graphen entspricht, an Stelle von natürlichen Zahlen zum Beispiel deren Binärdarstellung.

Auch wenn sich Beweise komplexitätstheoretischer Aussagen in der Regel konkreter Repräsentationen der Eingabe bedienen, versucht man Aussagen und 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 unter anderem die Auswahl eines geeigneten universellen Maschinenmodells von Bedeutung.

Problemgröße

Hat man ein Problem formal definiert (zum Beispiel das Problem des Handlungsreisenden in Form eines Graphen mit Kantengewichten), so möchte man Aussagen darüber treffen, wie sich ein Algorithmus bei der Berechnung der Problemlösung in Abhängigkeit von der Schwierigkeit des Problems verhält. Im Allgemeinen sind bei der Beurteilung der Schwierigkeit des Problems viele verschiedene Aspekte zu betrachten. Dennoch gelingt es häufig, wenige skalare Größen zu finden, die das Verhalten des Algorithmus im Hinblick auf den Ressourcenverbrauch maßgeblich beeinflussen. Diese Größen bezeichnet man als die Problemgröße. In aller Regel entspricht diese der Eingabelänge (bei einer konkret gewählten Repräsentation der Eingabe).

Man untersucht nun das Verhalten des Algorithmus in Abhängigkeit von der Problemgröße. Die Komplexitätstheorie interessiert sich für die Frage: Wie viel Mehrarbeit ist für wachsende Problemgrößen notwendig? Steigt der Aufwand (in Relation zur Problemgröße) zum Beispiel linear, polynomial, exponentiell oder gar überexponentiell?

So kann man beim Problem des Handlungsreisenden die Problemgröße als Anzahl der vorgegebenen Orte definieren (wobei man vernachlässigt, dass auch die vorgegebenen Streckenlängen verschieden große Eingabegrößen aufweisen können). Dann ist dieses Problem für die Problemgröße 2 trivial, da es hier überhaupt nur eine mögliche Lösung gibt und diese folglich auch optimal sein muss. Mit zunehmender Problemgröße wird ein Algorithmus jedoch mehr Arbeit leisten müssen.

Bester, schlechtester und durchschnittlicher Fall für Problemgrößen

Auch innerhalb einer Problemgröße lassen sich verschiedene Verhaltensweisen von Algorithmen beobachten. So hat das Problem des Handlungsreisenden 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 in der Regel unendlich viele Instanzen gleicher Größe für ein Problem gibt, gruppiert man diese zumeist grob in drei Gruppen: bester, schlechtester und durchschnittlicher Fall. Diese stehen für die Fragen:

• Bester Fall: Wie arbeitet der Algorithmus (in Bezug auf die in Frage stehende Ressource) im günstigsten Fall?
• Schlechtester Fall: Wie arbeitet der Algorithmus im schlimmsten Fall?
• Durchschnittlicher Fall: 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 bester, schlechtester und durchschnittlicher Fälle bezieht sich stets auf eine feste Eingabelänge. 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. Man spricht 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 die unteren Schranken von besonderem Interesse: Man möchte zeigen, dass ein bestimmtes Problem mindestens einen bestimmten Ressourcenverbrauch beansprucht und es folglich keinen Algorithmus geben kann, der das Problem mit geringeren Ressourcen entscheidet. Solche Ergebnisse helfen, Probleme nachhaltig bezüglich ihrer Schwierigkeit zu separieren. Jedoch sind bisher nur vergleichsweise wenige aussagekräftige untere Schranken bekannt. Der Grund hierfür liegt in der Problematik, dass sich Untersuchungen unterer Schranken stets auf alle denkbaren Algorithmen für ein Problem beziehen müssen; also auch auf Algorithmen, die heute noch gar nicht bekannt sind.

Im Gegensatz dazu gelingt der Nachweis von oberen Schranken in der Regel durch die Analyse konkreter Algorithmen. Durch den Beweis der Existenz auch nur eines Algorithmus, der die obere Schranke einhält, ist der Nachweis bereits erbracht.

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 Dezimalzahlen dürfte sich ungleich schneller errechnen lassen als das Produkt zweier hundertstelliger Dezimalzahlen. Bei einem uniformen Kostenmaß würden 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 Dezimalzahl n im Wesentlichen durch log ₂(n) Binärziffern darstellen lässt. Man wählt zur Repräsentation der Operanden Binärziffern aus und definiert die erlaubten booleschen 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 verschiedene Berechnungsparadigmen: der pragmatischste Typ ist sicher der der deterministischen Maschinen; weiterhin gibt es den in der Theorie besonders relevanten Typ der nichtdeterministischen Maschinen; weiterhin gibt es noch probabilistische Maschinen, alternierende und andere. In der Regel kann man jedes Maschinenmodell mit jedem der obigen Paradigmen definieren. Einige Paradigmen, so zum Beispiel der Nichtdeterminismus, modellieren dabei einen Typ, der der Theorie vorbehalten bleiben muss, da man den Nichtdeterminismus in der dort definierten Form physikalisch nicht bauen kann, (sie „erraten“ einen richtigen Pfad in einem Berechnungsbaum), lassen sich jedoch häufig leicht 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:

• 

  Turingmaschine

• 

  Registermaschine

• 

  Kellerautomat

• 

  Endlicher Automat

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

Die erweiterte Church-Turing-These

Für die Verwendung von Maschinenmodellen in der Komplexitätstheorie ist eine Erweiterung der Church-Turing-These von Bedeutung, die auch als erweiterte Church-Turing-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. Auch diese These ist nicht beweisbar; im Gegensatz zur gewöhnlichen Church-Turing-These wäre es aber möglich, sie durch ein Gegenbeispiel zu widerlegen.

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 zum Beispiel der Eingabespeicher in die Speicherplatzanalyse einbezogen, so könnte kein Problem in weniger als $\mathcal{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 Zeit T entscheidet, eine neue Turingmaschine konstruieren lässt, die das Problem in Zeit weniger als $\varepsilon \cdot T$ entscheidet. Dabei kann ε > 0 beliebig klein gewählt sein. Das bedeutet nichts anderes, als dass sich jede Turingmaschine, die ein bestimmtes Problem löst, um einen beliebigen konstanten Faktor beschleunigen lässt. Der Preis für diese Beschleunigung besteht in einer stark vergrößerten Arbeitsalphabetgröße und Zustandsmenge der verwendeten Turingmaschine (letztlich also „Hardware“).

Diese Beschleunigung wird unabhängig von der Problemgröße erreicht. Es ergibt daher keinen Sinn, konstante Faktoren bei der Betrachtung von Problemen zu berücksichtigen – solche Faktoren ließen sich durch Anwendung der Beschleunigungstechnik wieder beseitigen. Die Vernachlässigung konstanter 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

Eine wesentliche Aufgabe der Komplexitätstheorie besteht darin, sinnvolle Komplexitätsklassen festzulegen, in diese die vorliegenden Probleme einzusortieren und Aussagen über die wechselseitigen Beziehungen zwischen den Klassen zu finden.

Einflussgrößen bei der Bildung von Komplexitätsklassen

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

• Das zugrunde liegende 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 $\mathcal{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: \mathbb{N} \rightarrow \mathbb{N}$ (Schrittzahl, Speicher usw. werden als natürliche Zahlen berechnet).
• $f(n+1) \geq f(n)$ (monotones Wachstum).
• Die Funktion f muss selbst in Zeit $\mathcal{O}(f)$ und mit Raum $\mathcal{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 (zum Beispiel als Turingmaschine) in Beweise einfließen und sollte sich daher für diese Zwecke „gutartig“ verhalten. An dieser Stelle soll nur darauf hingewiesen werden, dass bei der Wahl der Schrankenfunktion eine gewisse Vorsicht walten muss, weil sonst bestimmte algorithmische Techniken nicht angewandt werden können.

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 $\mathcal{O}(1)$ logarithmisch $\mathcal{O}(\log n)$ polylogarithmisch $\mathcal{O}(\log^k n)$ für $k \geq 1$ linear $\mathcal{O}(n)$ n-log-n $\mathcal{O}(n \log n)$ quadratisch $\mathcal{O}(n^2)$ polynomial $\mathcal{O}(n^k)$ für $k \geq 1$ exponentiell $\mathcal{O}(d^n)$ 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.^[1]

Zeithierarchiesatz

Der Zeithierarchiesatz besagt:

$\operatorname{DTIME}\big(f(n) \big) \subsetneq \operatorname{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)$

Dies bedeutet also, dass man die Zeitressource um einen Faktor log ²(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:

$\operatorname{DSPACE}\big(f(n)\big) \subsetneq \operatorname{DSPACE} \big(f(n) \sdot \log(f(n)) \big)$

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 ²(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 zum Beispiel 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 logarithmisch beschränktem Raum entscheidbare Sprachen.
• PSPACE: Deterministisch mit polynomial beschränktem Raum entscheidbare Sprachen.
• NSPACE(f): Allgemeine Schreibweise für nichtdeterministische Raumklassen.
• NL: Nichtdeterministisch mit logarithmisch beschränktem Raum entscheidbare Sprachen.
• CSL: Kontextsensitive Sprachen sind die nichtdeterministisch mit linear beschränktem Raum entscheidbaren Sprachen.

Siehe auch: Liste von Komplexitätsklassen

Komplementbildungen

Für jede Komplexitätsklasse lässt sich ihre Komplementklasse bilden: Die Komplementklasse enthält genau die Komplemente der ursprünglichen Klasse. Dagegen kann man auch das Komplement einer Klasse betrachten, das sind alle Mengen, die in dieser Klasse nicht sind; diese Mengen sind in der Regel viel schwerer als die der ursprünglichen Komplexitätsklasse. Die Komplementklasse hingegen besitzt mit der ursprünglichen Klasse in der Regel einen nichtleeren Durchschnitt. 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 in der Regel 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 Akzeptanz anders definiert ist.

Beispielsweise ist bislang unbekannt, ob NP = CoNP gilt. P = CoP ist wahr, da das zugrunde liegende Modell deterministisch ist und hier die akzeptierenden und ablehnenden Zustände in den Berechnungen einfach ausgetauscht werden können, wie im vorherigen Absatz angesprochen. So sehen wir sofort, dass P im Durchschnitt von NP und CoNP enthalten ist. Ob dieser Durchschnitt genau P ist, ist nicht bekannt.

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 eine 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 zu 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 wüssten wir, dass es selbst für NP-vollständige Probleme Algorithmen geben muss, die mit polynomiellem Zeitaufwand arbeiten.

Da umgekehrt die Definition der NP-Vollständigkeit Algorithmen voraussetzt, mit denen es gelingt, beliebige Probleme aus NP in polynomieller Zeit auf NP-vollständige Probleme zu reduzieren, wären mit der polynomialen Lösbarkeit auch nur eines einzigen NP-vollständigen Problems sofort sämtliche Probleme der Klasse NP in polynomieller Zeit lösbar. Dies hätte eine Problemlösekraft in der gesamten Informatik zur Folge, wie sie auch durch noch so große Fortschritte in der Hardware-Entwicklung nicht erreicht werden kann.

Andererseits ist für bestimmte Anwendungsfälle eine Lösung des P-NP-Problems im Sinne von P = NP eher unerwünscht. Beispielsweise würden asymmetrische Verschlüsselungsverfahren erheblich an Sicherheit verlieren, da diese dann in Polynomialzeit gebrochen werden könnten.

Der Fall P ≠ NP

Würde das P-NP-Problem im Sinne von P ≠ NP gelöst, so wäre klar, dass weitere Bemühungen, polynomielle Lösungen für NP-vollständige Probleme zu finden, sinnlos wären. Man kann sich leicht vorstellen, dass aufgrund 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.

In vielen Theoremen wird heute jedoch angenommen, dass P ≠ NP gilt, denn nur so kann ohne einen Beweis der Gleichheit trotzdem effektive Forschungsarbeit geleistet werden. Man sucht nach Auswegen durch Approximationen und Heuristiken, nach Problemeinschränkungen, die die Praxis nicht vernachlässigen.

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. 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

Das folgende Inklusionsdiagramm gibt einen – recht groben – Überblick über die Zusammenhänge zwischen Klassen der Berechenbarkeitstheorie, der Chomsky-Hierarchie und den bedeutendsten Komplexitätsklassen.

Geschichte der Komplexitätstheorie

Nachdem in den vorhergehenden Abschnitten zahlreiche Grundbegriffe und wichtige Ergebnisse der Komplexitätstheorie erläutert wurden, wird 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 Hisao 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 Edwin 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öffentlichte Manuel Blum das Speedup-Theorem. 1969 folgt das Union-Theorem von Edward M. McCreight und Albert R. Meyer. Und 1972 veröffentlicht Allan 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. Alan Cobham zeigt, dass die Polynomialzeit robust unter der Wahl des Maschinenmodells ist (was man heute unter der erweiterten Church-Turing These zusammenfasst). Darüber hinaus erweisen sich viele mathematische Funktionen als in Polynomialzeit berechenbar.

Erforschung der Klasse NP

Die Klasse NP tritt zuerst bei Jack 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 Stephen Cook auf Tautologien (aussagenlogische 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 Yao das Konzept der Falltürfunktionen (trapdoor functions) vor, die eine spezielle Art von Einwegfunktionen (one way functions) darstellen, und zeigt deren grundlegende Wichtigkeit in der Kryptographie auf. Jedoch genügt für die Schwierigkeit, einen Code zu knacken, die Worst-Case-Betrachtungsweise der Komplexitätsklassen wie NP nicht. Es dürfen vielmehr auch keine Algorithmen existieren, die diese Probleme in einem signifikanten Anteil aller Fälle effizient lösen. Dies korrespondiert zum Modell der probabilistischen Turingmaschine und motiviert die Einführung randomisierter Komplexitätsklassen wie ZPP, RP oder BPP (alle eingeführt von John T. Gill, 1977).

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.

Weblinks

• Complexity Zoo -- „Zoo“ der Komplexitätsklassen

Literatur

• Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. 1. Auflage. Springer, Berlin 2003, ISBN 3-540-00161-1.
• K. Rüdiger Reischuk: Komplexitätstheorie - Band I: Grundlagen: Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. 2. Auflage. Teubner, Stuttgart/Leipzig 1999, ISBN 3-519-12275-8.
• Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass. 1995, ISBN 0-201-53082-1.
• Lance Fortnow, Steve Homer: A Short History of Computational Complexity. Online-Manuskript (PDF, 225 kB)
• Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. The MIT Press/Elsevier, Amsterdam 1994, ISBN 0-262-72020-5.
• Juris Hartmanis, Richard Edwin Stearns: On the computational complexity of algorithms. In: Trans. American Mathematical Society. 117/1965, S. 285-306, ISSN 0002-9947.
• Ding-Zhu Du, Ker-I Ko: Theory of Computational Complexity. John Wiley & Sons, New York 2000, ISBN 0-471-34506-7.
• Michael R. Garey, David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness. Freeman, New York 2003, ISBN 0-7167-1045-5.
• Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3. (International Edition)

Fußnoten

1. ↑ 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 unter anderem, 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.

Dieser Artikel wurde am 13. November 2006 in dieser Version in die Liste der exzellenten Artikel aufgenommen.