Liste von Komplexitätsklassen

Dies i​st eine Liste v​on Komplexitätsklassen, d​ie in d​er Komplexitätstheorie betrachtet werden.

Die Klassen verwenden i​n ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle s​ind Turingmaschinen; d​iese können deterministisch, nichtdeterministisch o​der probabilistisch arbeiten. Als Komplexitätsmaß werden v​or allem Zeitkomplexität u​nd Speicherplatzkomplexität betrachtet (in Abhängigkeit v​on der Problemgröße bzw. Eingabelänge n). Die Abschätzung v​on konkreter Laufzeit o​der Speicherplatzverbrauch w​ird durch d​ie Landau-Notation ausgedrückt.

Für j​ede Klasse i​st – f​alls möglich – d​ie Definition i​n der DTIME-, DSPACE-, NTIME- o​der NSPACE-Notation, s​owie eine k​urze natürlichsprachige Erklärung angegeben.

Bezeichnung	Definition	Beschreibung
#P
#P-vollständig		Die schwierigsten Probleme in #P.
AM		In Polynomialzeit durch ein Arthur-Merlin-Protokoll (s. engl) lösbar.
BPP		In Polynomialzeit mit geringer Fehlerwahrscheinlichkeit durch eine probabilistische Turingmaschine lösbar.
BQP		In Polynomialzeit mit geringer Fehlerwahrscheinlichkeit durch einen Quantencomputer lösbar.
Co-NP		Lösungen sind in Polynomialzeit falsifizierbar.
DSPACE(f(n))		Von einer deterministischen Turingmaschine auf O(f(n)) Platz lösbar.
DTIME(f(n))		Von einer deterministischen Turingmaschine in O(f(n)) Zeit lösbar.
E	${\displaystyle \bigcup _{c>0}{\mbox{DTIME}}(2^{cn})}$	Von einer deterministischen Turingmaschine in Exponentialzeit mit linearem Exponenten lösbar.
ESPACE	${\displaystyle \bigcup _{c>0}{\mbox{DSPACE}}(2^{cn})}$	Von einer deterministischen Turingmaschine auf linear exponentiellem Platz lösbar.
EXP		Andere Bezeichnung für EXPTIME.
EXPSPACE	${\displaystyle \bigcup _{c>0}{\mbox{DSPACE}}(2^{n^{c}})}$	Von einer deterministischen Turingmaschine auf exponentiellem Platz lösbar.
EXPTIME	${\displaystyle \bigcup _{c>0}{\mbox{DTIME}}(2^{n^{c}})}$	Von einer deterministischen Turingmaschine in exponentieller Zeit lösbar.
FP		In Polynomialzeit berechenbare Funktionen.
FPT		Von einem parametrisierten Algorithmus lösbar (Fixed Parameter Tractable)
L	${\displaystyle {\mbox{DSPACE}}(\log(n))}$	Von einer Turingmaschine auf logarithmischem Platz lösbar.
LOGSPACE		Andere Bezeichnung für L.
NC		In polylogarithmischer Zeit auf einer parallelen Registermaschine mit polynomiell vielen Prozessoren lösbar.
NE	${\displaystyle \bigcup _{c>0}{\mbox{NTIME}}(2^{cn})}$	Von einer nichtdeterministischen Turingmaschine in linear exponentieller Zeit lösbar.
NESPACE	${\displaystyle \bigcup _{c>0}{\mbox{NSPACE}}(2^{cn})}$	Von einer nichtdeterministischen Turingmaschine auf linear exponentiellem Platz lösbar.
NEXP		Andere Bezeichnung für NEXPTIME
NEXPSPACE	${\displaystyle \bigcup _{c>0}{\mbox{NSPACE}}(2^{n^{c}})}$	Von einer nichtdeterministischen Turingmaschine auf exponentiellem Platz lösbar.
NEXPTIME	${\displaystyle \bigcup _{c>0}{\mbox{NTIME}}(2^{n^{c}})}$	Von einer nichtdeterministischen Turingmaschine in exponentieller Zeit lösbar.
NL	${\displaystyle \bigcup _{c>0}{\mbox{NSPACE}}(\log ^{c}(n))}$	Von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz lösbar.
NLOGSPACE		Andere Bezeichnung für NL.
NP	${\displaystyle \bigcup _{c>0}{\mbox{NTIME}}(n^{c})}$	Von einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösbar.
NP-vollständig		Die schwierigsten Probleme in NP.
NP-schwierig		Probleme, auf die sich alle NP-Probleme in Polynomialzeit reduzieren lassen.
NPSPACE	${\displaystyle \bigcup _{c>0}{\mbox{NSPACE}}(n^{c})}$	Von einer nichtdeterministischen Turingmaschine auf polynomiellem Platz lösbar. Entspricht PSPACE.
NSPACE(f(n))		Von einer nichtdeterministischen Turingmaschine auf O(f(n)) Platz lösbar.
NTIME(f(n))		Von einer nichtdeterministischen Turingmaschine in O(f(n)) Zeit lösbar.
P	${\displaystyle \bigcup _{c>0}{\mbox{DTIME}}(n^{c})}$	Von einer deterministischen Turingmaschine in Polynomialzeit lösbar.
P-vollständig		Die schwierigsten Probleme in P.
POLYKERNEL		Parametrisierte Probleme, deren Instanzen (I,k) Problemkerne haben, deren Größe durch ein Polynom in k beschränkt ist.
PH		Die Vereinigung aller Klassen in der Polynomialzeithierarchie.
PP		Von einer probabilistischen Turingmaschine in Polynomialzeit lösbar, die Antwort ist in mehr als der Hälfte der Fälle richtig.
PSPACE	${\displaystyle \bigcup _{c>0}{\mbox{DSPACE}}(n^{c})}$	Von einer deterministischen Turingmaschine auf polynomiellem Platz lösbar. (Entspricht NPSPACE)
PSPACE-vollständig		Die schwierigsten Probleme in PSPACE.
RL		Von einer probabilistischen Turingmaschine auf logarithmischen Platz lösbar („Ja“-Antwort ist immer, „Nein“-Antwort ist meistens richtig).
RP		Von einer probabilistischen Turingmaschine in polynomieller Zeit lösbar („Ja“-Antwort ist immer, „Nein“-Antwort ist meistens richtig).
SL		Probleme, die auf USTCON log-space-reduzierbar sind. Entspricht L.
W[n]		Probleme, die von einem Weft n Schaltnetz gelöst werden können
W[n,h]		Probleme, die von einem Weft n Schaltnetz mit Höhe h gelöst werden können
ZPP		Probleme, die probabilistisch von einer NTM mit immer richtigen Antwort aber u. U. in von average case abweichender Laufzeit gelöst werden

Weblinks

• Complexity Zoo – Liste von Komplexitätsklassen und ihrer Beziehungen untereinander