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ändigDie schwierigsten Probleme in #P.AMIn Polynomialzeit durch ein Arthur-Merlin-Protokoll (s. engl) lösbar.BPPIn Polynomialzeit mit geringer Fehlerwahrscheinlichkeit durch eine probabilistische Turingmaschine lösbar.BQPIn Polynomialzeit mit geringer Fehlerwahrscheinlichkeit durch einen Quantencomputer lösbar.Co-NPLö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.EVon einer deterministischen Turingmaschine in Exponentialzeit mit linearem Exponenten lösbar. ESPACEVon einer deterministischen Turingmaschine auf linear exponentiellem Platz lösbar.EXPAndere Bezeichnung für EXPTIME.EXPSPACEVon einer deterministischen Turingmaschine auf exponentiellem Platz lösbar.EXPTIMEVon einer deterministischen Turingmaschine in exponentieller Zeit lösbar.FPIn Polynomialzeit berechenbare Funktionen.FPTVon einem parametrisierten Algorithmus lösbar (Fixed Parameter Tractable)LVon einer Turingmaschine auf logarithmischem Platz lösbar.LOGSPACEAndere Bezeichnung für L.NCIn polylogarithmischer Zeit auf einer parallelen Registermaschine mit polynomiell vielen Prozessoren lösbar.NEVon einer nichtdeterministischen Turingmaschine in linear exponentieller Zeit lösbar.NESPACEVon einer nichtdeterministischen Turingmaschine auf linear exponentiellem Platz lösbar.NEXPAndere Bezeichnung für NEXPTIMENEXPSPACEVon einer nichtdeterministischen Turingmaschine auf exponentiellem Platz lösbar.NEXPTIMEVon einer nichtdeterministischen Turingmaschine in exponentieller Zeit lösbar.NLVon einer nichtdeterministischen Turingmaschine auf logarithmischem Platz lösbar.NLOGSPACEAndere Bezeichnung für NL.NPVon einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösbar.NP-vollständigDie schwierigsten Probleme in NP.NP-schwierigProbleme, auf die sich alle NP-Probleme in Polynomialzeit reduzieren lassen.NPSPACEVon 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.PVon einer deterministischen Turingmaschine in Polynomialzeit lösbar.P-vollständigDie schwierigsten Probleme in P.POLYKERNELParametrisierte Probleme, deren Instanzen (I,k) Problemkerne haben, deren Größe durch ein Polynom in k beschränkt ist.PHDie Vereinigung aller Klassen in der Polynomialzeithierarchie.PPVon einer probabilistischen Turingmaschine in Polynomialzeit lösbar, die Antwort ist in mehr als der Hälfte der Fälle richtig.PSPACEVon einer deterministischen Turingmaschine auf polynomiellem Platz lösbar. (Entspricht NPSPACE)PSPACE-vollständigDie schwierigsten Probleme in PSPACE.RLVon einer probabilistischen Turingmaschine auf logarithmischen Platz lösbar („Ja“-Antwort ist immer, „Nein“-Antwort ist meistens richtig).RPVon einer probabilistischen Turingmaschine in polynomieller Zeit lösbar („Ja“-Antwort ist immer, „Nein“-Antwort ist meistens richtig).SLProbleme, die auf USTCON log-space-reduzierbar sind. Entspricht L.W[n] Probleme, die von einem Weft n Schaltnetz gelöst werden könnenW[n,h] Probleme, die von einem Weft n Schaltnetz mit Höhe h gelöst werden könnenZPPProbleme, 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
! Komplexitatsklassen