Komplexitätsklasse

In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands. Bei Problemen wird dabei stets das „kostengünstigste“ Lösungsverfahren angenommen. Der Aufwand ist im Allgemeinen abhängig von der „Größe“ der Eingabe, wie viele Elemente sie umfasst. Abgeschätzt wird der asymptotische Aufwand, also für sehr viele Eingabeelemente. Dabei zeigt sich, dass die Probleme bzgl. ihres Aufwands Gruppen bilden, deren Aufwand für große Eingabemengen auf ähnliche Weise anwächst; diese Gruppen werden Komplexitätsklassen genannt. Eine Komplexitätsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschränkten Berechnungsmodell berechnen lassen.

Definiert wird eine Komplexitätsklasse durch eine obere Schranke für den Bedarf einer bestimmten Ressource unter Voraussetzung eines Berechnungsmodells. Die am häufigsten betrachteten Ressourcen sind die Anzahl der notwendigen Berechnungsschritte zur Lösung eines Problems (Zeitkomplexität) oder der Bedarf an Speicherplatz (Raum- oder Platzkomplexität). Gemessen wird der Ressourcenbedarf in der Regel durch sein asymptotisches Verhalten an der Obergrenze (dem worst case) in Abhängigkeit von der Länge der Eingabe (Problemgröße).

Auch andere Maße des Ressourcenbedarfs sind möglich, etwa der statistische Mittelwert über alle möglichen Eingaben. Dieses Maß ist jedoch formal nur schwer zu analysieren.

Da durch eine Komplexitätsklasse nur eine obere Grenze für den Ressourcenbedarf festgelegt ist, wird somit für ein gegebenes Berechnungsmodell eine Hierarchie von Komplexitätsklassen gebildet, wobei weniger mächtige Klassen jeweils vollständig in den jeweils höheren Komplexitätsklassen enthalten sind. Zudem können durch formale Methoden auch über unterschiedliche Berechnungsmodelle oder Ressourcen definierte Klassen zueinander in Bezug gesetzt werden.