Komplexitätstheorie

Grundidee und Ziel

Die Komplexitätstheorie ist ein Teilgebiet der theoretischen Informatik. Sie untersucht, wie viel Ressourcen algorithmisch lösbare Probleme auf formalen Rechnermodellen benötigen. Die wichtigsten Ressourcen sind Rechenzeit und Speicherplatz; manchmal betrachtet man auch speziellere Größen wie die Größe eines Schaltkreises oder die Zahl benötigter Prozessoren bei parallelen Algorithmen.

Die Komplexität eines Algorithmus ist sein Ressourcenverbrauch. Die Komplexität eines Problems ist die Komplexität desjenigen Algorithmus, der dieses Problem mit dem geringstmöglichen Ressourcenverbrauch löst. Damit fragt die Komplexitätstheorie nicht zuerst, ob ein Problem überhaupt lösbar ist, sondern wie aufwendig seine Lösung ist.

Sie unterscheidet sich dadurch von der Berechenbarkeitstheorie, die untersucht, welche Probleme prinzipiell algorithmisch gelöst werden können. Das zentrale Ziel der Komplexitätstheorie ist die Klassifikation lösbarer Probleme, besonders die Abgrenzung zwischen effizient lösbaren Problemen und inhärent schwierigen Problemen. Sie zeigt damit auch, bei welchen Problemen die Informatik sinnvoll nach effizienten Algorithmen suchen kann und wann eher Näherungsverfahren oder andere Strategien nötig sind.

Innerhalb der theoretischen Informatik gilt die Komplexitätstheorie neben der Berechenbarkeitstheorie und der Theorie der formalen Sprachen als einer der drei Hauptbereiche. Ihre Methoden wirken auch in andere Gebiete hinein, etwa in die Automatentheorie sowie in den Entwurf und die Analyse von Algorithmen und Datenstrukturen.

Probleme, Instanzen und Größe

Der zentrale Gegenstand der Komplexitätstheorie sind Probleme, meist Entscheidungsprobleme. Ein Entscheidungsproblem verlangt für jede Eingabe eine Ja/Nein-Antwort. Oft wird es als formale Sprache beschrieben: Jede Probleminstanz wird als Wort über einem Alphabet kodiert, und die Sprache besteht aus genau den Wörtern, die zu Ja-Instanzen gehören. Die Aufgabe ist dann das Wortproblem: Man muss entscheiden, ob ein gegebenes Wort zur Sprache gehört.

Beispiel: Beim Problem, ob ein Graph zusammenhängend ist, kann ein Wort eine Darstellung eines Graphen sein. Die zu entscheidende Sprache enthält genau die Wörter, die zusammenhängende Graphen darstellen.

Neben Entscheidungsproblemen gibt es Berechnungsprobleme. Dabei wird nicht nur Ja oder Nein gefragt, sondern eine Lösung berechnet. Das Multiplikationsproblem ist zum Beispiel eine Abbildung \mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N} :(a,b)\mapsto a\cdot b. Viele Optimierungsprobleme sind ebenfalls Berechnungsprobleme: Man sucht ein Maximum oder Minimum einer Kostenfunktion. Beim Problem des Handlungsreisenden soll etwa eine Route minimaler Gesamtlänge gefunden werden. Für die Definition vieler Komplexitätsklassen verwendet man trotzdem bevorzugt Entscheidungsprobleme.

Wichtig ist der Unterschied zwischen Problem und Probleminstanz. Ein Problem ist die allgemeine Fragestellung, eine Instanz ist eine konkrete vollständige Eingabe. Beim Handlungsreisendenproblem könnte eine Instanz fragen, ob es eine Route durch die Landeshauptstädte Deutschlands mit höchstens 2000 km Länge gibt. Komplexitätstheoretisch interessant sind Probleme mit unendlich vielen Instanzen, weil bei endlich vielen Instanzen ein Programm bloß vorberechnete Antworten nachschlagen könnte.

Probleme und Instanzen werden über Alphabete kodiert, häufig über dem binären Alphabet mit 0 und 1. Graphen können zum Beispiel durch Bitfolgen beschrieben werden, etwa über eine Adjazenzmatrix; natürliche Zahlen durch ihre Binärdarstellung. Aussagen sollen möglichst unabhängig von der konkreten Repräsentation bleiben, solange Darstellungen ohne zu großen Aufwand ineinander überführt werden können.

Die Problemgröße ist meist die Eingabelänge einer kodierten Instanz. Man untersucht, wie der Ressourcenverbrauch wächst, wenn die Problemgröße wächst: linear, polynomial, exponentiell oder noch stärker. Innerhalb derselben Größe unterscheidet man häufig bester Fall, durchschnittlicher Fall, amortisierter Fall und schlechtester Fall. Besonders wichtig ist das asymptotische Verhalten für immer größere Eingaben. Dabei betrachtet man obere Schranken, also höchstens benötigte Ressourcen, und untere Schranken, also mindestens notwendige Ressourcen. Untere Schranken sind besonders schwer zu beweisen, weil sie alle denkbaren Algorithmen ausschließen müssen, auch unbekannte.

Maschinenmodelle und Kosten

Um Ressourcenverbrauch exakt zu untersuchen, verwendet die Komplexitätstheorie abstrakte Maschinenmodelle statt realer Computer. Ein Maschinenmodell legt fest, welche Arbeitsschritte ein Algorithmus ausführen darf, wie Speicher benutzt wird und ob parallele Verarbeitung möglich ist. Eine Kostenfunktion ordnet den erlaubten Befehlen Kostenwerte zu.

Häufig setzt man für jede Befehlsausführung den Kostenwert 1 an. Das heißt uniformes Kostenmaß. Es ist sinnvoll, wenn die Operationen ähnlich aufwendig sind und die Operanden nicht stark unterschiedlich groß werden. Wenn zum Beispiel Zahlen mit sehr unterschiedlicher Stellenzahl auftreten, kann ein logarithmisches Kostenmaß realistischer sein. Dabei wird berücksichtigt, dass sich eine Dezimalzahl n im Wesentlichen durch \log _{2}(n) viele Binärziffern darstellen lässt.

Wichtige Maschinenmodelle sind die Turingmaschine, die Registermaschine, der Kellerautomat und der endliche Automat. Für parallele Probleme verwendet man auch parallele Varianten, besonders die parallele Registermaschine.

Es gibt verschiedene Berechnungsmodi. Deterministische Maschinen folgen immer eindeutig dem nächsten Schritt. Nichtdeterministische Maschinen können in der Theorie mehrere Berechnungspfade betrachten und sozusagen einen richtigen Pfad in einem Berechnungsbaum finden; in dieser Form sind sie physikalisch nicht realisierbar, aber theoretisch sehr wichtig. Außerdem gibt es probabilistische, alternierende und weitere Maschinen.

Die erweiterte Church-Turing-These besagt, dass alle universellen Maschinenmodelle in Bezug auf die Rechenzeit bis auf polynomielle Faktoren gleich mächtig sind. Diese These ist nicht beweisbar, könnte aber durch ein Gegenbeispiel widerlegt werden. Sie erlaubt in der Komplexitätstheorie eine relativ freie Wahl des Maschinenmodells.

Für Speicherplatzanalysen modifiziert man Maschinenmodelle oft so, dass der Eingabespeicher nur gelesen und die Ausgabe nur geschrieben werden darf. Dadurch werden Ein- und Ausgabe nicht als Arbeitsspeicher mitgezählt. Sonst könnte kein Problem in weniger als {\mathcal {O}}(n) Platz gelöst werden, weil die Eingabe selbst Länge n hat.

Landau-Notation und Klassenbildung

Die Komplexitätstheorie beschreibt Größenordnungen des Zeit- oder Speicherbedarfs meist mit der Landau- oder O-Notation. Man spricht dann von Zeitkomplexität oder Platzkomplexität. Dabei werden konstante Faktoren und lineare Faktoren oft ausgeblendet, weil sie stark vom Maschinenmodell, Compiler oder der Hardware abhängen und für das asymptotische Wachstum wenig aussagen.

Das wichtigste Symbol ist {\mathcal {O}} für obere Schranken. Die Aussage f\in {\mathcal {O}}(g), oft geschrieben als f(n)={\mathcal {O}}(g(n)), bedeutet: Es gibt eine Konstante c>0 und ein n_{0}\in \mathbb {N}, sodass für alle n>n_{0} gilt: f(n)\leq c\cdot g(n). Der Aufwand f(n) wächst also höchstens um einen konstanten Faktor stärker als g(n). Für untere Schranken wird \Omega verwendet.

Eine Begründung für das Ignorieren konstanter Faktoren liefert das Speedup-Theorem. Vereinfacht sagt es: Zu jeder Turingmaschine, die ein Problem in Zeit T entscheidet, lässt sich eine neue Turingmaschine konstruieren, die dasselbe Problem in weniger als \varepsilon \cdot T Zeit entscheidet, wobei \varepsilon >0 beliebig klein sein kann. Der Preis ist eine stark vergrößerte Arbeitsalphabetgröße und Zustandsmenge.

Komplexitätsklassen fassen Probleme nach Ressourcenschranken zusammen. Einfluss haben dabei das Maschinenmodell, der Berechnungsmodus, die betrachtete Ressource, das Kostenmaß und die Schrankenfunktion. Beispielsweise bezeichnet DTIME(f) die Klasse aller Probleme, die auf einer deterministischen Turingmaschine in Zeit {\mathcal {O}}(f) entschieden werden können.

Schrankenfunktionen sollen meist echte Komplexitätsfunktionen sein: f\colon \mathbb {N} \rightarrow \mathbb {N}, monoton wachsend mit f(n+1)\geq f(n), und selbst in Zeit {\mathcal {O}}(f) sowie Raum {\mathcal {O}}(f) berechenbar. Übliche Schranken sind konstant {\mathcal {O}}(1), logarithmisch {\mathcal {O}}(\log n), polylogarithmisch {\mathcal {O}}(\log ^{k}n) für k\geq 1, linear {\mathcal {O}}(n), linearithmisch {\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 und faktoriell {\mathcal {O}}(n!).

Hierarchiesätze zeigen, dass mehr Ressourcen tatsächlich mehr lösbare Probleme erlauben können. Der Zeithierarchiesatz lautet \operatorname {DTIME}(f(n))\subsetneq \operatorname {DTIME}(f(n)\cdot \log ^{2}(f(n))). Der Raumhierarchiesatz lautet \operatorname {DSPACE}(f(n))\subsetneq \operatorname {DSPACE}(f(n)\cdot \log(f(n))). Diese Sätze gelten jeweils für denselben Berechnungsmodus und eine einzelne Ressource.

Wichtige Zeitklassen sind DTIME(f), P, EXPTIME, NTIME(f), NP, NEXPTIME und NC. Wichtige Raumklassen sind DSPACE(f), L, PSPACE, NSPACE(f), NL und CSL. Zu jeder Klasse K kann man außerdem eine Komplementklasse CoK bilden, die die Komplemente der Sprachen aus K enthält. Für deterministische Klassen gilt in der Regel K = CoK; zum Beispiel ist P = CoP. Für NP ist unbekannt, ob NP = CoNP gilt.

Das P-NP-Problem

Das P-NP-Problem ist eines der wichtigsten ungelösten Probleme der Komplexitätstheorie. Es fragt, ob die Klasse P gleich der Klasse NP ist.

P enthält die Sprachen, die deterministisch in Polynomialzeit entscheidbar sind. Die Probleme in P gelten in der Regel als praktisch lösbar, weil ihr Zeitaufwand höchstens polynomiell wächst und deterministische Maschinen realisierbar sind. Oft findet man Algorithmen mit Polynomen niedrigen Grades.

NP enthält Probleme, die auf nichtdeterministischen Maschinen in Polynomialzeit lösbar sind. Gleichwertig kann man NP über Verifikation beschreiben: Ein Verifikationsalgorithmus erhält neben der Eingabe einen Zeugen oder ein Zertifikat. Für eine Ja-Instanz muss es mindestens einen Zeugen geben, mit dem der Algorithmus positiv antwortet; für eine Nein-Instanz darf kein Zeuge positiv akzeptiert werden. Wenn es einen Verifikationsalgorithmus gibt, der mit einem Zeugen polynomieller Länge in polynomieller Zeit arbeitet, liegt das Problem in NP.

Ein Beispiel ist das Erfüllbarkeitsproblem SAT. Es fragt, ob es für eine boolesche Formel eine Belegung der Variablen gibt, sodass die Formel wahr ist. Ein Zeuge kann ein Vektor sein, der die Variablenbelegung kodiert. Für eine gegebene Belegung lässt sich effizient prüfen, ob die Formel wahr wird. Das Finden der Belegung ist nicht Aufgabe des Verifikationsalgorithmus.

Besonders wichtig sind NP-vollständige Probleme. Sie gelten für große Instanzen als praktisch unlösbar und kommen in vielen Bereichen der Informatik vor. Trotzdem sind nicht alle Probleme in NP schwer, denn P ist in NP enthalten.

Falls P = NP wäre, gäbe es auch für NP-vollständige Probleme Algorithmen mit polynomiellem Zeitaufwand. Wegen der Definition der NP-Vollständigkeit würde die polynomielle Lösbarkeit eines einzigen NP-vollständigen Problems bedeuten, dass alle Probleme in NP in Polynomialzeit lösbar wären. Das hätte enorme Folgen für die Informatik. Gleichzeitig wäre es für manche Anwendungen unerwünscht, etwa für asymmetrische Verschlüsselungsverfahren, weil diese dann in Polynomialzeit gebrochen werden könnten.

Falls P ≠ NP wäre, wäre klar, dass es keine polynomiellen Lösungen für NP-vollständige Probleme gibt. Viele Theoreme nehmen heute P ≠ NP an, obwohl es nicht bewiesen ist. In der Praxis sucht man deshalb häufig nach Approximationen, Heuristiken oder geeigneten Einschränkungen der Probleme.

Geschichtliche Entwicklung

Eine wichtige Grundlage war Alan Turings Konstruktion der Turingmaschine im Jahr 1936. Sie erwies sich später als flexibles Modell für die Analyse von Algorithmen. Erste informelle komplexitätstheoretische Untersuchungen stammen von John Myhill (1960), Raymond Smullyan (1961) und Hisao Yamada (1962), die sich mit speziellen zeit- und raumbeschränkten Problemklassen beschäftigten.

Als wichtiger Beginn der eigentlichen komplexitätstheoretischen Forschung gilt die Arbeit On the computational complexity of algorithms von Juris Hartmanis und Richard E. Stearns aus dem Jahr 1965. Sie definierten Zeit- und Platzkomplexität quantitativ, wählten die Mehrband-Turingmaschine als Grundlage und erarbeiteten erste Hierarchiesätze.

Weitere grundlegende Ergebnisse folgten: 1967 veröffentlichte Manuel Blum das Speedup-Theorem, 1969 Edward M. McCreight und Albert R. Meyer das Union-Theorem, und 1972 Allan Borodin das Gap-Theorem. In dieser frühen Phase wurde auch die Klasse P als Klasse der praktisch lösbaren Probleme formuliert. Alan Cobham zeigte, dass Polynomialzeit robust gegenüber der Wahl des Maschinenmodells ist.

Die Klasse NP wurde zunächst von Jack Edmonds informell beschrieben. Mit Reduzierbarkeit und NP-Vollständigkeit entstand ein zentrales Forschungsfeld. Der Satz von Cook (1971) zeigte, dass das Erfüllbarkeitsproblem SAT NP-vollständig ist. Richard Karp arbeitete 1972 die Technik der Reduktion weiter aus. Unabhängig davon entwickelte Leonid Levin 1973 in der damaligen Sowjetunion eine Theorie der NP-Vollständigkeit, die im Westen lange unbeachtet blieb. 1979 veröffentlichten Michael R. Garey und David S. Johnson ein Buch mit 300 NP-vollständigen Problemen.

Für Kryptographie und probabilistische Modelle wurden randomisierte Komplexitätsklassen wichtig. Andrew Yao stellte 1982 Falltürfunktionen vor, eine spezielle Art von Einwegfunktionen. Randomisierte Klassen wie PP, ZPP, RP und BPP wurden bereits 1977 von John T. Gill eingeführt. Später kamen auch Komplexitätsklassen für die Quanteninformationstheorie hinzu.