西安市档案局开展“三严三实”专题教育主题实践活动

百度 需要提醒的是，报考人员须在2018年3月30日9：00前在报名网站进行网上缴费。

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

Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese k?nnen deterministisch, nichtdeterministisch oder probabilistisch arbeiten. Als Komplexit?tsma? werden vor allem Zeitkomplexit?t und Speicherplatzkomplexit?t betrachtet (in Abh?ngigkeit von der Problemgr??e bzw. Eingabel?nge n). Die Absch?tzung von konkreter Laufzeit oder Speicherplatzverbrauch 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.

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	$\bigcup _{c>0}{\mbox{DTIME}}(2^{cn})$	Von einer deterministischen Turingmaschine in Exponentialzeit mit linearem Exponenten l?sbar.
ESPACE	$\bigcup _{c>0}{\mbox{DSPACE}}(2^{cn})$	Von einer deterministischen Turingmaschine auf linear exponentiellem Platz l?sbar.
EXP		Andere Bezeichnung für EXPTIME.
EXPSPACE	$\bigcup _{c>0}{\mbox{DSPACE}}(2^{n^{c}})$	Von einer deterministischen Turingmaschine auf exponentiellem Platz l?sbar.
EXPTIME	$\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	${\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	$\bigcup _{c>0}{\mbox{NTIME}}(2^{cn})$	Von einer nichtdeterministischen Turingmaschine in linear exponentieller Zeit l?sbar.
NESPACE	$\bigcup _{c>0}{\mbox{NSPACE}}(2^{cn})$	Von einer nichtdeterministischen Turingmaschine auf linear exponentiellem Platz l?sbar.
NEXP		Andere Bezeichnung für NEXPTIME
NEXPSPACE	$\bigcup _{c>0}{\mbox{NSPACE}}(2^{n^{c}})$	Von einer nichtdeterministischen Turingmaschine auf exponentiellem Platz l?sbar.
NEXPTIME	$\bigcup _{c>0}{\mbox{NTIME}}(2^{n^{c}})$	Von einer nichtdeterministischen Turingmaschine in exponentieller Zeit l?sbar.
NL	$\bigcup _{c>0}{\mbox{NSPACE}}(\log ^{c}(n))$	Von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz l?sbar.
NLOGSPACE		Andere Bezeichnung für NL.
NP	$\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	$\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	$\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	$\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