Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen. Die Komplexität eines Problems ist wiederum die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst.
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, deren Ressourcenverbrauch in der Praxis bewältigt werden kann, von der Menge der inhärent schwierigen Probleme abzugrenzen.
Inhaltsverzeichnis
1 Einordnung in die Theoretische Informatik
2 Probleme aus Sicht der Komplexitätstheorie
2.1 Entscheidungsprobleme als formale Sprachen
2.2 Berechnungsprobleme als Abbildungen
2.3 Probleminstanzen
2.4 Problemrepräsentationen
2.5 Problemgröße
2.6 Bester, schlechtester und durchschnittlicher Fall für Problemgrößen
2.7 Untere und obere Schranken für Probleme
3 Maschinenmodelle in der Komplexitätstheorie
3.1 Kostenfunktionen
3.2 Kostenmaße
3.3 Maschinenmodelle und Probleme
3.4 Häufig eingesetzte Maschinenmodelle
3.5 Die erweiterte Church-Turing-These
3.6 Modellmodifikationen für Speicherplatzanalysen
4 Verwendung und Rechtfertigung der O-Notation
5 Bildung von Komplexitätsklassen
5.1 Einflussgrößen bei der Bildung von Komplexitätsklassen
5.2 Anforderungen an Schrankenfunktionen
5.3 Hierarchiesätze
5.3.1 Zeithierarchiesatz
5.3.2 Raumhierarchiesatz
5.3.3 Wofür die Hierarchiesätze nicht gelten
5.4 Wichtige Zeitklassen
5.5 Wichtige Raumklassen
5.6 Komplementbildungen
6 Das P-NP-Problem und seine Bedeutung
6.1 Die Klasse P: Praktisch lösbare Probleme
6.2 Die Klasse NP: Praktisch (vermutlich) nicht effizient lösbare Probleme
6.3 Der Fall P = NP
6.4 Der Fall P ≠ NP
6.5 Konsequenzen für die Komplexitätstheorie
7 Sprachen und Komplexitätsklassen
8 Geschichte der Komplexitätstheorie
8.1 Grundlagen
8.2 Beginn der komplexitätstheoretischen Forschung
8.3 Erforschung der Klasse NP
8.4 Randomisierte Komplexitätsklassen
9 Literatur
10 Weblinks
11 Fußnoten
Einordnung in die Theoretische Informatik |
Die Komplexitätstheorie innerhalb 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, zu denen andere Disziplinen der Informatik überhaupt sinnvollerweise nach effizienten Lösungen suchen sollten, und motiviert so die Entwicklung praxistauglicher 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, und zwar in der Regel Entscheidungsprobleme, deren Instanzen eine Ja/Nein-Antwort erfordern. Ein Entscheidungsproblem wird dabei oft als formale Sprache dargestellt. Man drückt jede Probleminstanz als Wort über einem Alphabet aus, d. h. als Folge von Zeichen aus diesem Alphabet. Die fragliche Sprache besteht aus den Wörtern, denen eine Instanz mit der Antwort „Ja“ entspricht. Die Aufgabe besteht dann in der Lösung des Wortproblems, also darin, für ein gegebenes Wort zu entscheiden, ob es zu der Sprache gehört oder nicht, und damit hat man auch die Antwort auf die entsprechende Probleminstanz gefunden.
Wenn zum Beispiel das Problem darin besteht zu entscheiden, ob ein Graph zusammenhängend ist oder nicht, dann wäre ein Wort eine Darstellung eines beliebigen Graphen. Die zugehörige zu entscheidende Sprache wäre die Menge der Wörter, die einen zusammenhängenden Graphen darstellen.
Man könnte annehmen, dass die Einschränkung auf Entscheidungsprobleme viele wichtige Probleme ausschließt. Es gibt jedoch zu allen im Sinne der Komplexitätstheorie relevanten Problemen auch ein entsprechendes Entscheidungsproblem. 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){displaystyle (a,b,c)}
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{displaystyle f}
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 eine allgemeine Fragestellung, eine Schablone, dar. Eine Instanz des Problems ist dann eine vollständige Fragestellung, welche die richtige Antwort (ja bzw. nein im Fall eines Entscheidungsproblems) festlegt.
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. In der Komplexitätstheorie interessiert man sich daher für Aussagen, die unabhängig von konkreten Instanzen sind.
Ein Problem wird so allgemein formuliert, dass es eine unendliche Menge von Probleminstanzen definiert, denn es ist nicht sinnvoll, nach der Komplexität einer endlichen Menge von Instanzen zu fragen; ein Programm könnte eine Liste von vorgefertigten Antworten enthalten und nur durch Tabellenzugriff die richtige Lösung ausgeben, was den Aufwand für die Ermittlung der Antworten nicht widerspiegelt.
Interessant wird es erst, wenn eine unendliche Menge von Instanzen gegeben ist und man einen Algorithmus finden will, der für jede Instanz die richtige Antwort berechnet.
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{displaystyle n=16}
- Bester Fall: Wie arbeitet der Algorithmus (in Bezug auf die in Frage stehende Ressource) im günstigsten Fall?
- Durchschnittlicher Fall: Wie arbeitet der Algorithmus durchschnittlich (wobei die zugrundegelegte Verteilung für die Berechnung eines Durchschnitts nicht immer offensichtlich ist)?
Amortisierter Fall: Wie arbeitet der Algorithmus im schlechtesten Fall bei einer Folge von Durchläufen?- Schlechtester Fall: Wie arbeitet der Algorithmus im schlimmsten Fall?
Die Funktionen in den Ergebnissen zu den Fragen sind, wenn sie scharf angegeben sind, aufsteigend geordnet, d. h.: ein Problem, das amortisiert bspw. quadratischen Bedarf hat, hat (höchstens) quadratischen Bedarf auch im Durchschnitt und im schlechtesten Fall keinen geringeren.
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 oberer 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.
Bei bestimmten Problemen, etwa der Komplexität von Verschlüsselungsverfahren, wird der Nachweis versucht, dass der zu erwartende Ressourcenverbrauch beim Versuch, den Code zu knacken, jedes Maß übersteigt. Für Probleme, die selbst mit einem Computer von der Größe der Erde nicht während der Lebensdauer der Erde zu lösen sind, wurde der Begriff transcomputationales Problem geprägt.
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 log2(n){displaystyle log _{2}(n)}
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{displaystyle M}
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 O(n){displaystyle {mathcal {O}}(n)}
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{displaystyle T}
Diese Beschleunigung wird unabhängig von der Problemgröße erreicht. Bei der Betrachtung des asymptotischen Verhaltens von Problemen ergibt es daher keinen Sinn, konstante Faktoren 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 O(f){displaystyle {mathcal {O}}(f)}
f:N→N{displaystyle fcolon mathbb {N} rightarrow mathbb {N} }(Schrittzahl, Speicher usw. werden als natürliche Zahlen berechnet).
f(n+1)≥f(n){displaystyle f(n+1)geq f(n)}(monotones Wachstum).
- Die Funktion f{displaystyle f}
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 in der Praxis auftretenden 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){displaystyle {mathcal {O}}(1)}  |
| logarithmisch | O(logn){displaystyle {mathcal {O}}(log n)}  |
| polylogarithmisch | O(logkn){displaystyle {mathcal {O}}(log ^{k}n)}  für k≥1{displaystyle kgeq 1} |
| linear | O(n){displaystyle {mathcal {O}}(n)} |
| linearithmisch | O(nlogn){displaystyle {mathcal {O}}(nlog n)}  |
| quadratisch | O(n2){displaystyle {mathcal {O}}(n^{2})}  |
| polynomial | O(nk){displaystyle {mathcal {O}}(n^{k})}  für k≥1{displaystyle kgeq 1} |
| exponentiell | O(dn){displaystyle {mathcal {O}}(d^{n})}  für d>1{displaystyle 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 (auch Separationssätze genannt), 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 bilden einige der frühesten Ergebnisse der Komplexitätstheorie. Es 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:
- DTIME(f(n))⊊DTIME(f(n)⋅log2(f(n))){displaystyle operatorname {DTIME} {big (}f(n){big )}subsetneq operatorname {DTIME} {big (}f(n)cdot log ^{2}(f(n)){big )}}
Es gibt also Probleme, deren asymptotischer Zeitbedarf auf einer deterministischen Turingmaschine innerhalb der Klasse DTIME(f(n)⋅log2(f(n))),{displaystyle operatorname {DTIME} {big (}f(n)cdot log ^{2}(f(n)){big )},}
Raumhierarchiesatz |
Der Raumhierarchiesatz besagt:
- DSPACE(f(n))⊊DSPACE(f(n)⋅log(f(n))){displaystyle operatorname {DSPACE} {big (}f(n){big )}subsetneq operatorname {DSPACE} {big (}f(n)cdot 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)){displaystyle log(f(n))}
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 K lässt sich ihre Komplementklasse CoK bilden: Die Komplementklasse enthält genau die Komplemente der Elemente der ursprünglichen Klasse. Fasst man K als Menge von Sprachen auf (K⊆P(Σ∗){displaystyle Ksubseteq {mathcal {P}}(Sigma ^{*})}
Im Gegensatz dazu kann man auch das Komplement einer Klasse K betrachten. Dieses enthält genau die Sprachen/Probleme aus einer gegebenen Grundmenge, die nicht in K sind; diese Probleme sind in der Regel viel schwerer als die in K. Die Komplementklasse CoK hingegen besitzt mit K in der Regel einen nichtleeren Durchschnitt.
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 zeitlichem Aufwand zu berechnen. Der zeitliche Aufwand zur Problemlösung wächst für die Probleme der Klasse P maximal polynomial. Oft lassen sich sogar Algorithmen finden, deren Zeitfunktionen Polynome niedrigen Grades sind. Da das gewählte Maschinenmodell dieser Zeitklasse deterministisch (und realisierbar) ist, entsprechen die Probleme der Klasse P auch bei nicht-banaler Größe in etwa den praktisch lösbaren Problemen.
Die Klasse NP: Praktisch (vermutlich) nicht effizient lösbare Probleme |
Die Algorithmen zur Lösung der Probleme in NP basieren 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. Auf einer deterministischen Maschine, wie es alle existierenden Computer sind, kann der Aufwand zu ihrer Berechnung mit wachsender Problemgröße mehr als polynomial ansteigen. Es gibt daher Probleme in NP, die für praktische Zwecke als nicht lösbar gelten. Dazu gehören die NP-vollständigen Probleme. In dieser Klasse finden sich Probleme aus fast allen Bereichen der Informatik, deren effiziente Lösung enorm wichtig wäre. Es sind aber nicht alle Probleme in NP schwer, weil NP auch die Klasse P enthält.
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 E. 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.
Literatur |
Sanjeev Arora & Boaz Barak: Computational Complexity. A Modern Approach. Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4.
- Ding-Zhu Du & Ker-I Ko: Theory of Computational Complexity. John Wiley & Sons, New York 2000, ISBN 0-471-34506-7.
Lance Fortnow & Steve Homer: A Short History of Computational Complexity. 14. November 2002 (PDF, 225 kB)
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.
Juris Hartmanis & Richard E. Stearns: On the computational complexity of algorithms. In: Transactions of the American Mathematical Society. Vol. 117, 1965, S. 285–306 (PDF; 2018 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.
Christos Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass. 1995, ISBN 0-201-53082-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.
Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3. (International Edition)
Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. 1. Auflage. Springer, Berlin 2003, ISBN 3-540-00161-1.
Weblinks |
Commons: Komplexitätstheorie – Sammlung von Bildern, Videos und Audiodateien
Complexity Zoo – Verzeichnis der wichtigsten Komplexitätsklassen
Fußnoten |
↑ 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.
