Satz 8 (Satz von Savitch)
Sei s(n) >= log(n) raumkonstruierbar, dann gilt
Satz 9 Platzhierarchiesatz
Sei s(n) >= log(n) raumkonstruierbare Funktion, dann gibt es eine Sprache in SPACE(s), die nicht mit Speicherbedarf o(s) entschieden werden kann. Also
Satz 10 (Zeithierarchiesatz)
Wichtige Komplexitätsklassen und Zuordnung?
Last changeda year ago
