Komplexitätsklasse

Definition und Bedeutung

Eine Komplexitätsklasse ist eine Menge von Problemen, die sich in einem bestimmten Berechnungsmodell unter einer festgelegten Ressourcenbeschränkung berechnen lassen. Die Komplexitätstheorie untersucht damit, wie aufwendig Probleme oder Algorithmen zu berechnen sind. Bei einem Problem wird stets das kostengünstigste bekannte beziehungsweise mögliche Lösungsverfahren zugrunde gelegt.

Der Ressourcenbedarf hängt normalerweise von der Größe der Eingabe ab, also etwa von der Anzahl ihrer Elemente. Betrachtet wird vor allem der asymptotische Aufwand: Entscheidend ist, wie sich der Bedarf bei sehr großen Eingaben entwickelt. Probleme, deren Aufwand auf ähnliche Weise wächst, werden zu Komplexitätsklassen zusammengefasst. Solche Klassen ermöglichen es, Probleme unabhängig von einzelnen kleinen Eingaben und weitgehend unabhängig von technischen Einzelheiten zu vergleichen.

Ressourcen, Schranken und Hierarchie

Eine Komplexitätsklasse wird durch eine obere Schranke für den Bedarf einer bestimmten Ressource in einem bestimmten Berechnungsmodell definiert. Die wichtigsten Ressourcen sind:

• Zeitkomplexität: die Anzahl der Berechnungsschritte, die zur Lösung eines Problems benötigt werden.
• Raum- oder Platzkomplexität: der benötigte Speicherplatz.

Der Ressourcenbedarf wird in der Regel durch sein asymptotisches Verhalten im ungünstigsten Fall, dem worst case, in Abhängigkeit von der Eingabelänge beschrieben. Grundsätzlich sind auch andere Maße möglich, beispielsweise der statistische Mittelwert über alle möglichen Eingaben. Dieser ist jedoch formal schwer zu analysieren.

Da eine Klasse nur eine obere Grenze festlegt, entsteht für ein Berechnungsmodell eine Hierarchie: Weniger mächtige Klassen sind vollständig in den jeweils höheren Klassen enthalten. Formale Methoden erlauben außerdem Vergleiche zwischen Klassen, die durch unterschiedliche Ressourcen oder Berechnungsmodelle definiert sind.

Bestimmung und Einteilung

Zur Beschreibung des Wachstums werden häufig Landau-Symbole verwendet. Sie abstrahieren von Einzelheiten einer Implementierung und von konstanten Faktoren. Solche Faktoren sind für die Einteilung meist unwichtig, weil sich auch reale Computer in ihrer Ausführungsgeschwindigkeit um einen konstanten Faktor unterscheiden können. Daher werden keine konkreten Zeiteinheiten benötigt.

Die genaue Komplexität eines Problems zu bestimmen ist schwierig: Dafür müsste man grundsätzlich alle möglichen Algorithmen berücksichtigen und beweisen, dass ein bestimmter Algorithmus optimal ist. Die Komplexität eines Algorithmus lässt sich nur für eine konkrete Implementierung auf einem Maschinenmodell feststellen, zum Beispiel auf einer Turingmaschine oder im Lambda-Kalkül. Auf verschiedenen Maschinenmodellen sind die Klassen einer Implementierung jedoch meistens ähnlich oder – abhängig vom Abstraktionsniveau – gleich.

Wichtige Unterscheidungen sind Zeit gegenüber Platz sowie deterministische gegenüber nichtdeterministischen Maschinen. Bei einer deterministischen Maschine ist der nächste Rechenschritt jeweils eindeutig festgelegt; eine nichtdeterministische Maschine darf gedanklich zwischen mehreren Möglichkeiten wählen. Informell gilt Platz als mächtiger als Zeit und Nichtdeterminismus meist als mächtiger als Determinismus, jedoch jeweils höchstens exponentiell mächtiger. Genauere Beziehungen beschreiben der Satz von Savitch sowie der Satz von Immerman und Szelepcsényi.

Reduktion, Schwere und Vollständigkeit

Eine Reduktion führt ein Problem A mit geringem Aufwand auf ein anderes Problem B zurück. Ist dies möglich, gehört A mindestens zur Komplexitätsklasse von B; B wird dann als schwerer als A bezeichnet.

Ein Problem A heißt K-schwer, wenn sich alle anderen Probleme der Komplexitätsklasse K auf A reduzieren lassen. Gehört dieses K-schwere Problem zugleich selbst zur Klasse K, heißt es K-vollständig. K-vollständige Probleme gehören somit zur Klasse und sind innerhalb des durch Reduktionen beschriebenen Vergleichs mindestens so schwer wie alle anderen Probleme dieser Klasse.

Typische Wachstumsraten

Die Beispiele verdeutlichen, wie verschieden der Aufwand mit der Eingabegröße wachsen kann:

• Rasenmähen besitzt bezogen auf die Fläche mindestens lineare Komplexität, weil die gesamte Fläche wenigstens einmal überfahren werden muss. Für n m² beträgt der Zeitaufwand n · Konstante Sekunden. Ein dreimal so großer Rasen benötigt daher dreimal so viel Zeit.
• Einfache „dumme“ Sortierverfahren haben häufig quadratische Zeitkomplexität. Benötigt man für n = 20 Bücher beispielsweise 15 Sekunden, dauert das Sortieren von zehnmal so vielen Büchern mit demselben Verfahren 100-mal so lange. Bei der 50-fachen Menge wird die 2500-fache Zeit benötigt.
• Die binäre Suche in einem Telefonbuch hat logarithmische Komplexität. Dabei wird der verbleibende Suchbereich immer in der Mitte geteilt und geprüft, ob der gesuchte Name davor oder dahinter liegt. Der Aufwand für n Einträge wächst mit log₂(n). Verdoppelt sich die Zahl der Einträge, ist genau ein zusätzlicher Suchschritt nötig, weil dieser den Suchbereich wieder auf die vorherige Größe halbiert.