Liste von Komplexitätsklassen

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden.

Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle, die wichtigsten sind Turingmaschinen, diese können deterministisch, nichtdeterministisch oder probabilistisch arbeiten. Als Komplexitätsmaß werden vor allem Zeitkomplexität und Platzkomplexität betrachtet, die Abstraktion von konkreter Laufzeit oder Platzverbrauch wird durch die Landau-Notation ausgedrückt.

Für jede Klasse ist -- falls möglich -- die Definition in der DTIME-, DSPACE-, NTIME- oder NSPACE-Notation sowie eine kurze natürlichsprachige Erklärung angegeben.

#P
#P-vollständig		Die schwierigsten Probleme in #P.
AM		In Polynomialzeit durch ein Arthur-Merlin-Protokoll 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	$\bigcup_{c>0}DTIME(2^{cn})$	Von einer deterministischen Turingmaschine in Exponentialzeit mit linearem Exponenten lösbar.
ESPACE	$\bigcup_{c>0}DSPACE(2^{cn})$	Von einer deterministischen Turingmaschine auf linear exponentiellem Platz lösbar.
EXP		Andere Bezeichnung für EXPTIME.
EXPSPACE	$\bigcup_{c>0}DSPACE(2^{n^c})$	Von einer deterministischen Turingmaschine auf exponentiellem Platz lösbar.
EXPTIME	$\bigcup_{c>0}DTIME(2^{n^c})$	Von einer deterministischen Turingmaschine in exponentieller Zeit lösbar.
FP		In Polynomialzeit berechenbare Funktionen.
L	$D S P A C E (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	$\bigcup_{c>0}NTIME(2^{cn})$	Von einer nichtdeterministischen Turingmaschine in linear exponentieller Zeit lösbar.
NESPACE	$\bigcup_{c>0}NSPACE(2^{cn})$	Von einer nichtdeterministischen Turingmaschine auf linear exponentiellem Platz lösbar.
NEXP		Andere Bezeichnung für NEXPTIME
NEXPSPACE	$\bigcup_{c>0}NSPACE(2^{n^c})$	Von einer nichtdeterministischen Turingmaschine auf exponentiellem Platz lösbar.
NEXPTIME	$\bigcup_{c>0}NTIME(2^{n^c})$	Von einer nichtdeterministischen Turingmaschine in exponentieller Zeit lösbar.
NL	$\bigcup_{c>0}NSPACE(\log^c(n))$	Von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz lösbar.
NLOGSPACE		Andere Bezeichnung für NL.
NP	$\bigcup_{c>0}NTIME(n^c)$	Von einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösbar.
NP-vollständig		Die schwierigsten Problem in NP.
NP-schwierig		Probleme, auf die sich alle NP-Probleme in Polynomialzeit reduzieren lassen.
NPSPACE	$\bigcup_{c>0}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	$\bigcup_{c>0}DTIME(n^c)$	Von einer deterministischen Turingmaschine in Polynomialzeit lösbar.
P-vollständig		Die schwierigsten Probleme in P.
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	$\bigcup_{c>0}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.
ZPP