Theorie der rechnerischen Komplexität - Wikipedia

Theorie der Informatik, die Probleme nach ihrer inhärenten Schwierigkeit klassifiziert.

Computational Complexity Theory konzentriert sich auf die Klassifizierung von rechnerischen Problemen nach ihrer inhärenten Schwierigkeit und auf das Zusammenfügen dieser Klassen. Ein Rechenproblem ist eine Aufgabe, die von einem Computer gelöst wird. Ein Rechenproblem ist durch mechanische Anwendung von mathematischen Schritten, beispielsweise eines Algorithmus, lösbar.

Ein Problem wird von Natur aus als schwierig angesehen, wenn für seine Lösung unabhängig vom verwendeten Algorithmus erhebliche Ressourcen erforderlich sind. Die Theorie formalisiert diese Intuition, indem sie mathematische Rechenmodelle einführt, um diese Probleme zu untersuchen und ihre rechnerische Komplexität zu quantifizieren, d. H. Die Menge an Ressourcen, die zu ihrer Lösung benötigt werden, wie Zeit und Speicher. Andere Maßeinheiten der Komplexität werden ebenfalls verwendet, wie beispielsweise der Kommunikationsumfang (verwendet in der Kommunikationskomplexität), die Anzahl von Gattern in einer Schaltung (in der Schaltungskomplexität verwendet) und die Anzahl von Prozessoren (in der parallelen Berechnung verwendet). Eine der Aufgaben der Theorie der rechnerischen Komplexität besteht darin, die praktischen Grenzen zu bestimmen, was Computer tun können und was nicht. Das P-versus-NP-Problem, eines der sieben Probleme des Millennium-Preises, widmet sich dem Gebiet der rechnerischen Komplexität. ^[1]

Eng verwandte Gebiete in der theoretischen Informatik sind die Analyse von Algorithmen und die Berechenbarkeitstheorie. Ein wesentlicher Unterschied zwischen der Analyse von Algorithmen und der rechnerischen Komplexitätstheorie besteht darin, dass die erstere dazu dient, die Menge an Ressourcen zu analysieren, die ein bestimmter Algorithmus benötigt, um ein Problem zu lösen, während die letztere eine allgemeinere Frage zu allen möglichen Algorithmen stellt, für die ein Algorithmus verwendet werden kann Löse das gleiche Problem. Genauer gesagt versucht die Theorie der rechnerischen Komplexität, Probleme zu klassifizieren, die mit entsprechend beschränkten Ressourcen gelöst werden können oder nicht. Das Auferlegen von Beschränkungen für die verfügbaren Ressourcen wiederum unterscheidet die rechnerische Komplexität von der Theorie der Berechenbarkeit: Die letztere Theorie fragt, welche Probleme im Prinzip algorithmisch gelöst werden können.

Computerprobleme [ edit ]

Eine reisende Verkäufer-Tour durch 14 deutsche Städte.

Problemstellungen [ edit ]

A Das Rechenproblem kann als unendliche Sammlung von Instanzen zusammen mit einer Lösung für jede Instanz betrachtet werden. Die Eingabezeichenfolge für ein Rechenproblem wird als Probleminstanz bezeichnet und sollte nicht mit dem Problem selbst verwechselt werden. In der Theorie der rechnerischen Komplexität bezieht sich ein Problem auf die zu lösende abstrakte Frage. Im Gegensatz dazu ist ein Fall dieses Problems eine ziemlich konkrete Äußerung, die als Eingabe für ein Entscheidungsproblem dienen kann. Betrachten Sie beispielsweise das Problem der Primalitätsprüfung. Die Instanz ist eine Zahl (z. B. 15) und die Lösung ist "Ja", wenn die Zahl Primzahl ist und ansonsten "Nein" (in diesem Fall ist 15 keine Primzahl und die Antwort ist "Nein"). Anders ausgedrückt ist die Instanz eine besondere Eingabe für das Problem, und die -Lösung ist die Ausgabe, die der gegebenen Eingabe entspricht.

Um den Unterschied zwischen einem Problem und einer Instanz noch deutlicher hervorzuheben, betrachten Sie die folgende Instanz der Entscheidungsversion des Problems des reisenden Händlers: Gibt es eine Route von höchstens 2000 Kilometern durch alle 15 größten Städte Deutschlands? Die quantitative Antwort auf diese spezielle Probleminstanz ist für die Lösung anderer Fälle der Problematik wenig hilfreich, beispielsweise um eine Rundfahrt durch alle Standorte in Mailand mit einer Gesamtlänge von höchstens 10 km anzufordern. Aus diesem Grund befasst sich die Komplexitätstheorie mit Rechenproblemen und nicht mit bestimmten Problemfällen.

Darstellung von Probleminstanzen [ edit ]

Bei der Betrachtung von Computerproblemen ist eine Probleminstanz eine Zeichenfolge über einem Alphabet. Normalerweise wird das Alphabet als das binäre Alphabet (d. H. Der Satz {0,1}) verstanden, und somit sind die Zeichenfolgen Bitfolgen. Wie in einem realen Computer müssen andere mathematische Objekte als Bitstrings geeignet codiert werden. Zum Beispiel können Ganzzahlen in binärer Notation dargestellt werden, und Graphen können direkt über ihre Adjazenzmatrizen oder durch Codieren ihrer Adjazenzlisten in binär codiert werden.

Auch wenn einige Beweise für komplexitätstheoretische Theoreme regelmäßig eine konkrete Wahl der Eingabecodierung voraussetzen, versucht man, die Diskussion abstrakt genug zu halten, um unabhängig von der Wahl der Codierung zu sein. Dies kann erreicht werden, indem sichergestellt wird, dass verschiedene Repräsentationen effizient ineinander umgewandelt werden können.

Entscheidungsprobleme als formale Sprachen [ edit ]

Ein Entscheidungsproblem hat nur zwei mögliche Ausgänge, ja oder nein (oder alternativ) 1 oder 0) auf einen beliebigen Eingang.

Entscheidungsprobleme sind eines der zentralen Untersuchungsobjekte der Komplexitätstheorie. Ein Entscheidungsproblem ist eine besondere Art von Rechenproblem, dessen Antwort entweder ja oder nein oder alternativ entweder 1 oder 0 ist. Ein Entscheidungsproblem kann als eine formale Sprache betrachtet werden, wo das Mitglieder der Sprache sind Instanzen, deren Ausgabe ja ist, und die Nichtmitglieder sind die Instanzen, deren Ausgabe nein ist. Das Ziel besteht darin, mit Hilfe eines Algorithmus zu entscheiden, ob eine gegebene Eingabezeichenfolge ein Mitglied der betrachteten formalen Sprache ist. Wenn der Algorithmus, der dieses Problem festlegt, die Antwort zurückgibt yes wird der Algorithmus die Eingabezeichenfolge annehmen, andernfalls wird die Eingabe zurückgewiesen.

Ein Beispiel für ein Entscheidungsproblem ist das folgende. Die Eingabe ist ein beliebiger Graph. Das Problem besteht darin, zu entscheiden, ob der angegebene Graph verbunden ist oder nicht. Die mit diesem Entscheidungsproblem verbundene formale Sprache ist dann die Menge aller verbundenen Graphen. Um eine genaue Definition dieser Sprache zu erhalten, muss entschieden werden, wie Graphen als binäre Zeichenfolgen codiert werden.

Funktionsprobleme [ edit ]

Ein Funktionsproblem ist ein Rechenproblem, bei dem eine einzelne Ausgabe (einer Gesamtfunktion) für jede Eingabe erwartet wird, die Ausgabe jedoch komplexer ist als das eines Entscheidungsproblems - das heißt, die Ausgabe ist nicht nur Ja oder Nein. Zu den bemerkenswerten Beispielen gehören das Problem des reisenden Verkäufers und das Problem der ganzzahligen Faktoren.

Es ist verlockend zu glauben, dass der Begriff der Funktionsprobleme viel reicher ist als der Begriff der Entscheidungsprobleme. Dies ist jedoch nicht wirklich der Fall, da Funktionsprobleme als Entscheidungsprobleme umgeformt werden können. Zum Beispiel kann die Multiplikation von zwei ganzen Zahlen als Satz von Tripeln ausgedrückt werden (19459022] a b c ), so dass die Beziehung a × b = c gilt. Die Entscheidung, ob ein gegebenes Tripel Mitglied dieser Menge ist, entspricht der Lösung des Problems der Multiplikation zweier Zahlen.

Messen der Größe einer Instanz [ edit ]

Um die Schwierigkeit der Lösung eines Rechenproblems zu messen, möchte man vielleicht wissen, wie viel Zeit der beste Algorithmus zur Lösung des Problems benötigt . Die Laufzeit kann jedoch im Allgemeinen von der Instanz abhängen. Insbesondere größere Instanzen erfordern mehr Zeit zum Lösen. Somit wird die Zeit, die zum Lösen eines Problems benötigt wird (oder der erforderliche Platz oder ein beliebiges Maß für die Komplexität) als Funktion der Größe der Instanz berechnet. Dies wird normalerweise als die Größe der Eingabe in Bits angesehen. Die Komplexitätstheorie interessiert sich dafür, wie Algorithmen mit einer Zunahme der Eingabegröße skalieren. Wie viel Zeit benötigt man zum Beispiel, um herauszufinden, ob ein Graph verbunden ist, um ein Problem für einen Graph mit 2 n Knoten zu lösen, verglichen mit der Zeit für einen Graph mit ? n Ecken?

Wenn die Eingangsgröße n ist, kann die Zeit als Funktion von n ausgedrückt werden. Da die Zeit, die für verschiedene Eingaben der gleichen Größe benötigt wird, unterschiedlich sein kann, wird die Zeitkomplexität T ( n ) für den ungünstigsten Fall als die maximale Zeit definiert, die über alle Eingaben der Größe n genommen wird ]. Wenn T ( n ) ein Polynom in n ist, dann wird der Algorithmus als ein Polynomialzeitalgorithmus bezeichnet. Cobhams These argumentiert, dass ein Problem mit einer realisierbaren Menge an Ressourcen gelöst werden kann, wenn es einen Polynomialzeitalgorithmus zulässt.

Maschinenmodelle und Komplexitätsmaße [ edit ]

Turing-Maschine [ edit ]

Eine Abbildung einer Turing-Maschine

A Die Turingmaschine ist ein mathematisches Modell einer allgemeinen Rechenmaschine. Es ist ein theoretisches Gerät, das Symbole auf einem Bandstreifen manipuliert. Turingmaschinen sind nicht als praktische Computertechnologie gedacht, sondern eher als allgemeines Modell einer Computermaschine - vom fortgeschrittenen Supercomputer bis zum Mathematiker mit Bleistift und Papier. Es wird angenommen, dass, wenn ein Problem durch einen Algorithmus gelöst werden kann, eine Turing-Maschine vorhanden ist, die das Problem löst. Dies ist in der Tat die Aussage der Church-Turing-These. Darüber hinaus ist es bekannt, dass alles, was mit anderen heute bekannten Rechenmodellen berechnet werden kann, wie z. B. einer RAM-Maschine, Conways Game of Life, Zellularautomaten oder einer beliebigen Programmiersprache, auf einer Turing-Maschine berechnet werden kann. Da Turing-Maschinen mathematisch einfach zu analysieren sind und von denen angenommen wird, dass sie so leistungsfähig sind wie jedes andere Berechnungsmodell, ist die Turing-Maschine das am häufigsten verwendete Modell in der Komplexitätstheorie.

Viele Arten von Turingmaschinen werden zur Definition von Komplexitätsklassen verwendet, wie deterministische Turingmaschinen, probabilistische Turingmaschinen, nicht deterministische Turingmaschinen, Quanten-Turingmaschinen, symmetrische Turingmaschinen und alternierende Turingmaschinen. Sie sind im Prinzip alle gleich mächtig, aber wenn Ressourcen (wie Zeit oder Raum) begrenzt sind, sind einige von ihnen möglicherweise mächtiger als andere.

Eine deterministische Turingmaschine ist die grundlegendste Turingmaschine, die zur Festlegung ihrer zukünftigen Aktionen einen festen Satz von Regeln verwendet. Eine probabilistische Turingmaschine ist eine deterministische Turingmaschine mit einem zusätzlichen Vorrat an Zufallsbits. Die Möglichkeit, probabilistische Entscheidungen zu treffen, hilft Algorithmen dabei, Probleme effizienter zu lösen. Algorithmen, die Zufallsbits verwenden, werden als randomisierte Algorithmen bezeichnet. Eine nicht-deterministische Turing-Maschine ist eine deterministische Turing-Maschine mit dem zusätzlichen Merkmal des Nicht-Determinismus, die es einer Turing-Maschine ermöglicht, aus einem gegebenen Zustand mehrere mögliche zukünftige Aktionen auszuführen. Eine Möglichkeit, den Nicht-Determinismus zu betrachten, besteht darin, dass sich die Turing-Maschine bei jedem Schritt in viele mögliche Berechnungspfade verzweigt. Wenn das Problem in einem dieser Zweige gelöst wird, soll es das Problem gelöst haben. Natürlich ist dieses Modell nicht als physikalisch realisierbares Modell gedacht, es ist nur eine theoretisch interessante abstrakte Maschine, die zu besonders interessanten Komplexitätsklassen führt. Beispiele finden Sie unter nicht deterministischer Algorithmus.

Andere Maschinenmodelle [ edit ]

Viele Maschinenmodelle, die sich von den Standard-Multiband-Turingmaschinen unterscheiden, wurden in der Literatur vorgeschlagen, zum Beispiel Direktzugriffsmaschinen. Überraschenderweise kann jedes dieser Modelle ohne zusätzliche Rechenleistung in ein anderes umgewandelt werden. Zeit und Speicherverbrauch dieser alternativen Modelle können variieren. ^[2] Allen diesen Modellen ist gemeinsam, dass die Maschinen deterministisch arbeiten.

Einige Berechnungsprobleme lassen sich jedoch anhand ungewöhnlicher Ressourcen leichter analysieren. Beispielsweise ist eine nicht deterministische Turing-Maschine ein Rechenmodell, das verzweigt werden kann, um viele verschiedene Möglichkeiten gleichzeitig zu prüfen. Die nicht-deterministische Turing-Maschine hat sehr wenig damit zu tun, wie wir physikalisch Algorithmen berechnen wollen, aber ihre Verzweigung erfasst viele der mathematischen Modelle, die wir analysieren möchten, so dass nicht-deterministische Zeit eine sehr wichtige Ressource für die Analyse von Berechnungsproblemen ist .

Komplexitätsmaße [ edit ]

Für eine genaue Definition dessen, was es bedeutet, ein Problem unter Verwendung einer bestimmten Zeit und eines bestimmten Raums zu lösen, eines Rechenmodells wie der deterministischen Turing-Maschine wird eingesetzt. Die -Zeit die eine deterministische Turing-Maschine M am Eingang x benötigt, ist die Gesamtzahl der Zustandsübergänge oder Schritte, die die Maschine macht, bevor sie stoppt und ausgibt antworte ja oder nein"). Eine Turing-Maschine M soll innerhalb der Zeit ( n ) arbeiten, wenn die von M benötigte Zeit bei jeder Längeneingabe erforderlich ist n ist höchstens f ( n ). Ein Entscheidungsproblem A kann zeitlich gelöst werden f ( n ), wenn eine Turing-Maschine existiert, die rechtzeitig arbeitet f () ] n ), das das Problem löst. Da die Komplexitätstheorie daran interessiert ist, Probleme anhand ihrer Schwierigkeit zu klassifizieren, werden Problemgruppen anhand einiger Kriterien definiert. Zum Beispiel wird die Menge der Probleme, die innerhalb einer bestimmten Zeit f ( n ) auf einer deterministischen Turing-Maschine lösbar sind, dann mit DTIME ( f [ n n) bezeichnet. )).

Für den Platzbedarf können analoge Definitionen gemacht werden. Obwohl Zeit und Raum die bekanntesten Komplexitätsressourcen sind, kann jedes Maß der Komplexität als Rechenressource betrachtet werden. Komplexitätsmaße werden sehr allgemein durch die Komplexitätsaxiome von Blum definiert. Andere in der Komplexitätstheorie verwendete Komplexitätsmaße umfassen Kommunikationskomplexität, Schaltungskomplexität und Entscheidungsbaumkomplexität.

Die Komplexität eines Algorithmus wird oft in einer großen O-Notation ausgedrückt.

Beste, schlechteste und durchschnittliche Fallkomplexität [ edit ]

Die beste, schlechteste und durchschnittliche Fallkomplexität bezieht sich auf drei verschiedene Arten der Messung der Zeitkomplexität (oder eines anderen Komplexitätsmaßes). von verschiedenen Eingängen der gleichen Größe. Da einige Eingaben der Größe n möglicherweise schneller zu lösen sind als andere, definieren wir die folgenden Komplexitäten:

1. Komplexität im besten Fall: Dies ist die Komplexität der Lösung des Problems für die beste Eingabe der Größe n .


2. Durchschnittliche Fallkomplexität: Dies ist die Komplexität der Lösung des Problems im Durchschnitt. Diese Komplexität wird nur in Bezug auf eine Wahrscheinlichkeitsverteilung über die Eingaben definiert. Wenn beispielsweise angenommen wird, dass alle Inputs der gleichen Größe gleich wahrscheinlich sind, kann die durchschnittliche Fallkomplexität in Bezug auf die gleichmäßige Verteilung über alle Inputs der Größe definiert werden n .


3. Amortized analysis : Die amortisierte Analyse berücksichtigt sowohl die kostspieligen als auch die weniger kostspieligen Operationen zusammen über die gesamte Reihe von Operationen des Algorithmus.


4. Komplexität im ungünstigsten Fall: Dies ist die Komplexität der Lösung des Problems für die schlechteste Eingabe der Größe n [19459023

Die Reihenfolge von billig nach teuer lautet: Best, durchschnittlich (diskrete Gleichverteilung), amortisiert, am schlechtesten.

Betrachten Sie zum Beispiel den deterministischen Sortieralgorithmus. Dies löst das Problem der Sortierung einer Liste von Ganzzahlen, die als Eingabe angegeben wird. Der ungünstigste Fall liegt vor, wenn die Eingabe in umgekehrter Reihenfolge sortiert wird und der Algorithmus für diesen Fall die Zeit O ( n ² ) benötigt. Wenn wir davon ausgehen, dass alle möglichen Permutationen der Eingabeliste gleich wahrscheinlich sind, beträgt die durchschnittliche Zeit zum Sortieren 0 ( n log n ). Der beste Fall tritt auf, wenn jede Verschwenkung die Liste in zwei Hälften teilt und auch O-Zeit ( n log n ) Zeit benötigt.

Ober- und Untergrenzen der Komplexität von Problemen [ edit ]

Um die Rechenzeit (oder ähnliche Ressourcen, wie z. B. den Raumverbrauch) zu klassifizieren, ist man daran interessiert, Upper und Proof zu beweisen untere Grenzen für die maximale Zeitdauer, die der effizienteste Algorithmus benötigt, um ein gegebenes Problem zu lösen. Die Komplexität eines Algorithmus wird normalerweise als die Worst-Case-Komplexität betrachtet, sofern nicht anders angegeben. Die Analyse eines bestimmten Algorithmus fällt in den Bereich der Analyse von Algorithmen. Um eine obere Schranke T ( n ) bezüglich der zeitlichen Komplexität eines Problems darzustellen, muss nur gezeigt werden, dass es einen bestimmten Algorithmus mit einer Laufzeit von höchstens T ( n ). Das Prüfen der unteren Grenzen ist jedoch viel schwieriger, da die unteren Grenzen eine Aussage über alle möglichen Algorithmen treffen, die ein gegebenes Problem lösen. Der Ausdruck "alle möglichen Algorithmen" umfasst nicht nur die heute bekannten Algorithmen, sondern jeden Algorithmus, der in der Zukunft entdeckt werden könnte. Um eine untere Schranke von T ( n ) für ein Problem darzustellen, muss gezeigt werden, dass kein Algorithmus eine geringere Zeitkomplexität als T ( n [19459023)habenkann]).

Ober- und Untergrenze werden normalerweise mit der großen O-Notation angegeben, wodurch konstante Faktoren und kleinere Terme verborgen werden. Dies macht die Grenzen unabhängig von den spezifischen Details des verwendeten Rechenmodells. Zum Beispiel, wenn T ( n ) = 7 n ² + 15 n + 40, in großer O-Notation eins würde schreiben T ( n ) = O ( n ² ).

Komplexitätsklassen [ edit ]

Definieren von Komplexitätsklassen [ edit

A ist eine Komplexitätsklasse von Problemen verwandter Komplexität. Einfachere Komplexitätsklassen werden durch folgende Faktoren definiert:

• Die Art des Rechenproblems: Die am häufigsten verwendeten Probleme sind Entscheidungsprobleme. Komplexitätsklassen können jedoch auf der Grundlage von Funktionsproblemen, Zählproblemen, Optimierungsproblemen, Versprechungsproblemen usw. definiert werden.


• Das Berechnungsmodell: Das am häufigsten verwendete Berechnungsmodell ist die deterministische Turing-Maschine, auf der jedoch viele Komplexitätsklassen basieren nicht deterministische Turingmaschinen, boolesche Schaltungen, Quanten-Turingmaschinen, monotone Schaltungen usw.


• Die Ressourcen (oder Ressourcen), die begrenzt werden, und die Grenzen: Diese beiden Eigenschaften werden normalerweise zusammen angegeben, z. B. "Polynomialzeit". "logarithmischer Raum", "konstante Tiefe" usw.

Einige Komplexitätsklassen haben komplizierte Definitionen, die nicht in dieses Framework passen. Daher hat eine typische Komplexitätsklasse die folgende Definition:

Die Menge der Entscheidungsprobleme, die durch eine deterministische Turing-Maschine innerhalb einer Zeit gelöst werden können f ( n ). (Diese Komplexitätsklasse ist als DTIME bekannt ( f ( n )).)

Aber die oben genannte Rechenzeit wird durch eine konkrete Funktion begrenzt f ( n ) ergibt häufig Komplexitätsklassen, die vom gewählten Maschinenmodell abhängen. Zum Beispiel die Sprache { xx | x ist eine beliebige binäre Zeichenfolge}, die auf einer Multi-Tape-Turing-Maschine in linearer Zeit gelöst werden kann, erfordert jedoch notwendigerweise eine quadratische Zeit im Modell von Single-Tape-Turing-Maschinen. Wenn wir Polynomialvariationen in der Laufzeit zulassen, heißt es in der Cobham-Edmonds-These, dass "die zeitlichen Komplexitäten in zwei vernünftigen und allgemeinen Berechnungsmodellen polynomial miteinander zusammenhängen" (Goldreich 2008, Kapitel 1.2). Dies bildet die Grundlage für die Komplexitätsklasse P, die die Menge der Entscheidungsprobleme darstellt, die von einer deterministischen Turingmaschine innerhalb der Polynomialzeit gelöst werden können. Die entsprechenden Funktionsprobleme sind FP.

Wichtige Komplexitätsklassen [ edit ]

Eine Darstellung der Beziehung zwischen Komplexitätsklassen

Viele wichtige Komplexitätsklassen können durch Begrenzung der vom Algorithmus verwendeten Zeit oder des Raums definiert werden. Einige wichtige Komplexitätsklassen von auf diese Weise definierten Entscheidungsproblemen sind folgende:

Komplexitätsklasse Berechnungsmodell Ressourcenbeschränkung Deterministische Zeit DTIME ( f ( n )) Deterministische Turingmaschine Zeit f ( n ) P Deterministische Turingmaschine Zeit Poly ( n ) EXPTIME Deterministische Turingmaschine Zeitpunkt 2 Poly ( n ) Nicht deterministische Zeit NTIME ( f ( n )) Nicht deterministische Turingmaschine Zeit f ( n ) NP Nicht deterministische Turingmaschine Zeit Poly ( n ) NEXPTIME Nicht deterministische Turingmaschine Zeitpunkt 2 poly ( n )

Komplexitätsklasse Berechnungsmodell Ressourcenbeschränkung Deterministischer Raum DSPACE ( f ( n )) Deterministische Turingmaschine Raumfahrt f ( n ) L Deterministische Turingmaschine Raum O (log n ) PSPACE Deterministische Turingmaschine Space Poly ( n ) EXPSPACE Deterministische Turingmaschine Raum 2 Poly ( n ) Nicht deterministischer Raum NSPACE ( f ( n )) Nicht deterministische Turingmaschine Raumfahrt f ( n ) NL Nicht deterministische Turingmaschine Raum O (log n ) NPSPACE Nicht deterministische Turingmaschine Space Poly ( n ) NEXPSPACE Nicht deterministische Turingmaschine Raum 2 Poly ( n )

Die logarithmischen Raumklassen berücksichtigen (notwendigerweise) nicht den Raum, der zur Darstellung des Problems erforderlich ist.

Es stellt sich heraus, dass PSPACE = NPSPACE und EXPSPACE = NEXPSPACE nach dem Satz von Savitch.

Weitere wichtige Komplexitätsklassen umfassen BPP, ZPP und RP, die mit probabilistischen Turing-Maschinen definiert werden; AC und NC, die über boolesche Schaltungen definiert werden; und BQP und QMA, die unter Verwendung von Quantenturingmaschinen definiert werden. #P ist eine wichtige Komplexitätsklasse für Zählprobleme (keine Entscheidungsprobleme). Klassen wie IP und AM werden mit Interactive Proof-Systemen definiert. ALL ist die Klasse aller Entscheidungsprobleme.

Hierarchietheoreme [ edit ]

Für die auf diese Weise definierten Komplexitätsklassen ist es wünschenswert zu beweisen, dass die Lockerung der Anforderungen an die Rechenzeit (sagen wir) tatsächlich eine größere Menge von Recheneinheiten definiert Probleme. Obwohl DTIME ( n ) in DTIME ( n ² ) enthalten ist, wäre es insbesondere interessant zu wissen, ob die Einbeziehung streng ist. Für Zeit- und Raumanforderungen wird die Antwort auf solche Fragen durch Zeit- und Raumhierarchietheorien gegeben. Sie werden als Hierarchiesätze bezeichnet, da sie eine korrekte Hierarchie für die definierten Klassen erzeugen, indem sie die jeweiligen Ressourcen einschränken. Es gibt also Paare von Komplexitätsklassen, so dass einer richtig in den anderen aufgenommen wird. Nachdem wir solche richtigen Einschlüsse abgeleitet haben, können wir quantitative Aussagen darüber machen, wie viel zusätzlicher Zeit- oder Raumaufwand erforderlich ist, um die Anzahl der zu lösenden Probleme zu erhöhen.

Genauer gesagt, der Theorem der Zeithierarchie besagt dies

${ displaystyle { mathsf {DSPACE}} { big (} f (n) { big)} subsetneq { mathsf {DSPACE}} { big (} f (n) cdot log (f (n)) { big)}}$