Nächste Seite: Unterschiedliche Problemvarianten Aufwärts: Hauptseite Theorie Vorherige Seite: Nichtdeterminismus (Ergänzung)   Inhalt

Komplexitätsklassen

---

Unterabschnitte

• Unterschiedliche Problemvarianten
  • Vorstellung mit Beispiel
  • Überführung ineinander am Beispiel des Cliquenproblems
  
  
• Zeitkomplexität
  • SAT - Guess and Check Methode
  • Primzahlen
  • Cliquenproblem
  • Zeitkomplexitätsklassen
  • P,NP,EXPTIME
  • NP EXPTIME
  • Polynomialzeit akzeptierende NTMs
  
  
• Platzkomplexität
  • PSPACE
  • SAT PSPACE
  • In-Place Acceptance PSPACE
  • NP PSPACE
  • PSPACE EXPTIME
  • Satz von Savitch:
  • Übersicht über die Komplexitätsklassen

---