Liste von Komplexitätsklassen

Liste von Komplexitätsklassen

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.

#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}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.
FPT Von einem parametrisierten Algorithmus lösbar (Fixed Parameter Tractable)
L 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}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 Probleme 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.
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}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

Weblinks

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

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Immerman und Szelepcseny — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist. Lange nahm man an, dass die Klasse NSPACE genauso wie die Klasse NTIME nicht unter dem… …   Deutsch Wikipedia

  • Satz von Immerman und Szelepcsény — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist. Lange nahm man an, dass die Klasse NSPACE genauso wie die Klasse NTIME nicht unter dem… …   Deutsch Wikipedia

  • Satz von Immerman und Szelepcsényi — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NL unter Komplementbildung abgeschlossen ist. Lange nahm man wie für die Klasse NTIME an, dass NL nicht unter dem Komplement abgeschlossen …   Deutsch Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • Aufwandsklasse — Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine Komplexitätsklasse durch eine obere Schranke für… …   Deutsch Wikipedia

  • Aufwandsklassen — Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine Komplexitätsklasse durch eine obere Schranke für… …   Deutsch Wikipedia

  • Komplexitätsklasse — Zusammenhang verschiedener Komplexitätsklassen Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine… …   Deutsch Wikipedia

  • Monte-Carlo-Integration — Monte Carlo Algorithmen sind randomisierte Algorithmen, die mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil… …   Deutsch Wikipedia

  • Monte-Carlo-Algorithmus — Monte Carlo Algorithmen sind randomisierte Algorithmen, die mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil… …   Deutsch Wikipedia

  • Faktorisierungsproblem — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”