Komplexitätsklasse

Verschiedene Komplexitätsklassen:

Zeitkomplexität

• TIME
• NTIME
• P
• NP
  • NP-Schwere
  • NP-Vollständigkeit
• coNP
• EXPTIME

Platzkomplexität

• SPACE
• NSPACE
• LSPACE
  • Satz BRANCHING-PROG in L
• NLSPACE
  • NL-Schwere
  • NL-Vollständigkeit
• PSPACE
  • NPSPACE
  • PSPACE-Vollständigkeit
  • PSPACE-Schwere
• EXPSPACE
  • EXPSPACE-Vollständigkeit

probabilistischen Komplexitätsklassen

• BPP
• RP
• coRP
• Null-Fehler probabilistische polynomielle Zeit

Quantum Klasses

• BQP