Komplexitätstheorie

Hier wird die Komplexitätstheorie im Sinne der Informatik abgehandelt. Zur Komplexitätstheorie im kybernetischen Sinne finden Sie mehr unter komplexe Systeme

---

Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen, sowie der Güte der sie lösenden Algorithmen. Die Untersuchung der Komplexität bezieht sich dabei auf den Ressourcenverbrauch der Algorithmen, meist auf die Rechenzeit oder den Speicherplatzbedarf. Die Komplexitätstheorie unterscheidet sich von der Berechenbarkeitstheorie, die sich mit der Frage beschäftigt, welche Probleme prinzipell algorithmisch gelöst werden können.

Probleme aus Sicht der Komplexitätstheorie

Probleme als formale Sprachen

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

Probleminstanzen

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

Problemrepräsentationen

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

Entscheidungsprobleme

Darüber hinaus verzichtet man in der Komplexitätstheorie oft darauf, Problemlösungen zu generieren, sondern begnügt sich mit der Antwort, ob ein Problem mit einem definierten Ressourcenaufwand lösbar ist oder nicht. So formulierte Probleme bezeichnet man auch als Entscheidungsprobleme. Die Motivation dieser Vereinfachung besteht darin, dass man sich im Rahmen der Komplexitätsanalyse eine Behandlung der Ausgabe einer Problemlösung ersparen möchte - zumal diese ohnehin meist von einer konkreten Repräsentation abhängig ist.

Problemgrößen

Hat man ein Problem mathematisch-formal definiert (z.B. das Traveling-Salesman-Problem in Form eines Graphen), so möchte man nun Aussagen darüber treffen, wie sich ein Algorithmus bei der Berechnung dieses Problems verhält. Potentiell wären viele verschiedene Aspekte des Problems zu betrachten. Normalerweise existiert jedoch eine Größe, die das Verhalten des Algorithmus im Hinblick auf den Ressourcenverbrauch maßgeblich beeinflusst. Diese Größe bezeichnet man als Problemgröße oder Eingabelänge. Man untersucht nun das Verhalten des Algorithmus im Hinblick auf unterschiedliche Problemgrößen. So ist beispielsweise das Traveling-Salesman-Problem für die Eingabelänge 2 trivial, da es hier überhaupt nur eine mögliche Lösung gibt und diese folglich auch optimal sein muss. Es ist jedoch zu erwarten, dass der Algorithmus für größere Eingaben mehr Arbeit leisten muss. Die Komplexitätstheorie interessiert sich nun für die Frage: Wieviel Mehrarbeit ist für wachsende Problemgrößen notwendig? Steigt der Aufwand zum Beispiel linear, polynomiell, exponentiell oder gar überexponentiell?

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

Auch innerhalb einer Problemgröße lassen sich verschiedene Verhaltensweisen von Algorithmen beobachten. So hat das Traveling-Salesman-Problem für die 16 deutschen Landeshauptstädte dieselbe Problemgröße n=16 wie das Finden einer Route durch 16 europäische Hauptstädte. Es ist keineswegs zu erwarten, dass ein Algorithmus unter den unterschiedlichen Bedingungen (selbst bei gleicher Problemgröße) jeweils gleich gut arbeitet. Da es jedoch praktisch unendlich viele Instanzen für ein Problem geben kann, gruppiert man diese zumeist grob in drei Gruppen: best case, worst case und average case. Diese stehen für die Fragen:

• Best case: Wie arbeitet der Algorithmus (in Bezug auf die in Frage stehende Ressource) im besten Fall?
• Worst case: Wie arbeitet der Algorithmus im schlimmsten Fall?
• Average case: Wie arbeitet der Algorithmus durchschnittlich (wobei die zugrundegelegte Verteilung für die Berechnung eines Durchschnitts nicht immer offensichtlich ist)?

Untere und obere Schranken für Probleme

Die Betrachtung von best, worst und average case bezieht sich auf zwar beliebige, aber feste Eingabelängen. Auch wenn die Betrachtung konkreter Eingabelängen in der Praxis von großem Interesse sein kann, ist diese Sichtweise für die Komplexitätstheorie meist nicht abstrakt genug. Welche Eingabelänge als groß oder praktisch relevant gilt, kann sich aufgrund technischer Entwicklungen sehr schnell ändern. Es ist daher gerechtfertigt, das Verhalten von Algorithmen in Bezug auf ein Problem gänzlich unabhängig von konkreten Eingabelängen zu untersuchen. Man betrachtet hierzu das Verhalten der Algorithmen für immer größer werdende, potentiell unendlich große Eingabelängen und spricht auch vom asymptotischen Verhalten des jeweiligen Algorithmus.

Bei dieser Untersuchung des asymptotischen Ressourcenverbrauchs spielen untere und obere Schranken eine zentrale Rolle. Man möchte also wissen, welche Ressourcen für die Entscheidung eines Problems mindestens und höchstens benötigt werden. Für die Komplexitätstheorie sind vor allem die unteren Schranken von Interesse: Man möchte zeigen, dass ein bestimmter Problemtyp mindestens einen bestimmten Ressourcenverbrauch beansprucht und es folglich keinen Algorithmus geben kann, der das Problem mit geringeren Ressourcen entscheiden kann. Im Gegensatz zum Nachweis von oberen Schranken, der in der Regel durch die Analyse konkreter Algorithmen erfolgen kann, muss sich also eine Untersuchung der unteren Schranken auch auf Algorithmen beziehen, die noch garnicht gefunden wurden, also auf die Menge aller, auch der noch unbekannten Algorithmen, die ein bestimmtes Problem entscheiden. Dies erfordert eine grundlegend andere, abstraktere Herangehensweise als die Analyse von bereits bekannten Algorithmen und gilt daher als schwer zugänglicher Teilbereich der Informatik.

Maschinenmodelle in der Komplexitätstheorie

Kostenfunktionen

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

Kostenmaße

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

Maschinenmodelle und Probleme

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

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

Häufig eingesetzte Maschinenmodelle

Besonders häufig eingesetzte Modelle sind:

• Endliche Automaten
• Kellerautomaten
• Registermaschinen
• Turingmaschinen

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

Modellmodifikationen für Speicherplatzanalysen

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

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

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

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

Verwendung und Rechtfertigung der O-Notation

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

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

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

Bildung von Komplexitätsklassen

Ein wesentliches Resultat der Komplexitätstheorie ist die Bildung von Komplexitätsklassen und Aussagen über deren wechselseitige Beziehungen. Die Einteilung von algorithmischen Problemen in Komplexitätsklassen erfolgt im Wesentlichen auf zwei Achsen:

• Zeitkomplexität und Platzkomplexität
• deterministisch und nichtdeterministisch

Anwendungsbereiche

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

Siehe auch

P/NP-Problem, NP, NC