Komplexitätsklasse

O Verschiedene Komplexitätsklassen:

Zeitkomplexität

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

Platzkomplexität

• SPACE
• ASPACE
• LSPACE
  • NLSPACE
    • NL-Schwere
    • NL-Vollständigkeit
  • coNL
  • ALSPACE
• PSPACE
  • PSPACE-Vollständigkeit
    • PSPACE-Schwere
  • NSPACE
  • APSPACE
• EXPSPACE
  • EXPSPACE-Vollständigkeit
  • EXPSPACE-Schwere

probabilistische Komplexitätsklassen

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

Quantum Klasses

• BQP

Orakel Komplexitätsklassen

• deterministisch polynomielle Zeit mit Orakel-TM
• nichtdeterministisch polynomielle Zeit mit Orakel-TM