Liste der Komplexitätsklassen

Das ist ein Liste von Komplexitätsklassen in Computerkomplexitätstheorie. Für andere Berechnungs- und Komplexitätsfächer siehe Liste der Berechnungs- und Komplexitätsthemen.

Viele dieser Klassen haben einen "Co" -Partner, der aus dem besteht Ergänzungen aller Sprachen in der Originalklasse. Wenn beispielsweise eine Sprache L in NP ist, ist die Komplement von L in Co-NP. (Dies bedeutet nicht, dass die Komplement von NP Co-NP ist-es gibt Sprachen, von denen bekannt ist, dass sie sich in beiden und anderen Sprachen befinden, von denen bekannt ist, dass sie in keinem beiden bekannt sind.)

"Die schwierigsten Probleme einer Klasse" beziehen sich auf Probleme, die zur Klasse gehören, so dass jedes andere Problem dieser Klasse darauf reduziert werden kann. Darüber hinaus ist die Reduktion auch ein Problem der gegebenen Klasse oder ihrer Untergruppe.

#P Zählen Sie Lösungen für ein NP -Problem
#P-Complete Die schwierigsten Probleme in #P
2-Exptime Lösbar in doppelt exponentieller Zeit
AC0 Eine Schaltungskomplexitätsklasse der begrenzten Tiefe
Acc0 Eine Schaltungskomplexitätsklasse von begrenzten Tiefen und Zählern
AC Eine Kreislaufkomplexitätsklasse
AH Die arithmetische Hierarchie
AP Die Klasse der Probleme Wechsel Turing -Maschinen kann in Polynomzeit lösen.[1]
APX Optimierungsprobleme die Annäherungsalgorithmen mit konstantem Annäherungsverhältnis haben[1]
BIN Lösbar in Polynomzeit von einem Arthur -Merlin -Protokoll[1]
BPP Lösbar in Polynomzeit von Randomisierte Algorithmen (Antwort ist wahrscheinlich richtig)
BQP Lösbar in Polynomzeit auf a Quantencomputer (Antwort ist wahrscheinlich richtig)
Co-NP "Nein" Antworten, die in Polynomzeit von einer nicht deterministischen Maschine überprüft werden können
CO-NP-Complete Die schwierigsten Probleme bei CO-NP
DSpace (f (n)) Lösbar durch eine deterministische Maschine mit Raum O (f (f (f (f)n)).
Time (f (f (n)) Lösbar durch eine deterministische Maschine in der Zeit o (f (f (n)).
E Lösbar in Exponentialzeit mit linearem Exponent
Elementar Die Vereinigung der Klassen in der Exponentielle Hierarchie
Espace Lösbar mit exponentiellem Raum mit linearem Exponent
Exp Gleich wie Expime
Expace Lösbar mit exponentiellem Raum
Nachfolger Lösbar in Exponentialzeit
Fnp Das Analogon von NP für Funktionsprobleme
FP Das Analogon von P für Funktionsprobleme
FPNp Das Analogon von pNp für Funktionsprobleme; die Heimat der Problem mit reisenden Verkäufern
Fpt Fix-Parameter-Traktable
Gapl Logspace-reduzierbar für die Berechnung der Ganzzahldeterminante einer Matrix
IP Lösbar in Polynomzeit von einem Interaktives Proof -System
L Lösbar mit logarithmischem (kleinem) Raum
Logcfl Logspace-reduzierbar auf a Kontextfreie Sprache
Ma Lösbar in Polynomzeit durch a Merlin -ARTHUR -Protokoll
NC Effizient lösbar (in Polylogarithmischer Zeit) auf parallelen Computern
Ne Lösbar durch eine nicht deterministische Maschine in Exponentialzeit mit linearem Exponent
Nespace Lösbar durch eine nicht deterministische Maschine mit exponentiellem Raum mit linearem Exponent
Nexp Gleich wie Nexptime
Nexpspace Lösbar durch eine nicht deterministische Maschine mit exponentiellem Raum
Nexptime Lösbar durch eine nicht deterministische Maschine in Exponentialzeit
Nl "Ja" Antworten mit logarithmischem Raum überprüft werden
Nicht Elementär Ergänzung von Elementar.
Np "Ja" Antworten in Polynomzeit überprüft (siehe Komplexitätsklassen P und NP))
NP-Complete Die schwierigsten oder ausdrucksstärksten Probleme in NP
NP-Easy Analog zu pNp zum Funktionsprobleme; Ein anderer Name für FPNp
NP-äquivalent Die schwierigsten Probleme bei FPNp
Np-harte Mindestens so hart wie jedes Problem in NP, aber nicht bekannt als in der gleichen Komplexitätsklasse
Nspace (f (n)) Lösbar durch eine nicht deterministische Maschine mit Raum O (f (f (n)).
Ntime (f (n)) Lösbar durch eine nicht deterministische Maschine in der Zeit o (f (f (n)).
P Lösbar in Polynomzeit
P-Complete Die schwierigsten Probleme in P, auf parallele Computer zu lösen
P/poly Lösbar in der Polynomzeit bei einer "Ratzeichenfolge", abhängig von der Eingangsgröße
PCP Probabilistisch prüfbarer Beweis
PH Die Vereinigung der Klassen in der Polynomhierarchie
PNp Lösbar in Polynomzeit mit einem Orakel für ein Problem in NP; Auch als Δ bekannt2P
Pp Probabilistisch polynomial (Antwort ist mit Wahrscheinlichkeit etwas mehr als ½) richtig)
Ppad Polynom -Paritätsargumente in gerichteten Graphen
Pr Lösbar durch rekursives Aufbau arithmetischer Funktionen.
PSPACE Lösbar mit Polynomraum.
PSPACE-Complete Die schwierigsten Probleme in der PSPACE.
PTAs Polynom-Zeit-Näherungsschema (eine Unterklasse von APX).
QIP Lösbar in der Polynomzeit durch ein quanteninteraktives Proof -System.
QMA Quantenanalog von Np.
R Lösbar in einer begrenzten Zeit.
BETREFFEND Probleme, auf die wir in einer begrenzten Zeit "Ja" antworten können, aber eine "Nein" -Anantwortung könnte nie kommen.
Rl Lösbar mit logarithmischem Raum durch randomisierte Algorithmen (keine Antwort ist wahrscheinlich richtig, ja ist sicherlich richtig)
RP Lösbar in der Polynomzeit durch randomisierte Algorithmen (keine Antwort ist wahrscheinlich richtig, ja ist sicherlich richtig)
Sl Probleme, die logarithmisch zu bestimmen sind, ob ein Pfad zwischen gegebenen Scheitelpunkten in einem ungerichteten Diagramm besteht. Im Oktober 2004 wurde festgestellt, dass diese Klasse tatsächlich gleich ist L.
S2P Ein Rundspiel mit gleichzeitigen Moves, die in Polynomzeit deterministisch referiert sind[2]
Tfnp Totalfunktionsprobleme in nicht deterministischer Polynomzeit lösbar. Ein Problem in dieser Klasse hat die Eigenschaft, die jeder Die Eingabe hat einen Ausgang, dessen Gültigkeit effizient überprüft werden kann, und die rechnerische Herausforderung besteht darin, eine gültige Ausgabe zu finden.
HOCH Eindeutige nicht deterministische Polytime-Funktionen.
Zpl Lösbar durch randomisierte Algorithmen (Antwort ist immer richtig, der durchschnittliche Raumnutzung ist logarithmisch)
Zpp Lösbar durch randomisierte Algorithmen (Antwort ist immer richtig, die durchschnittliche Laufzeit ist Polynom)

Verweise

  1. ^ a b c Sanjeev Arora, Boaz Barak (2009), Rechenkomplexität: ein moderner Ansatz, Cambridge University Press; 1 Ausgabe, ISBN 978-0-521-42426-4
  2. ^ "S2P: Zweite Ebene der symmetrischen Hierarchie ". Komplexitätszoo der Stanford University. Archiviert von das Original Am 2012-10-14. Abgerufen 2011-10-27.

Externe Links

  • Komplexitätszoo - Liste von über 500 Komplexitätsklassen und deren Eigenschaften