Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
GThI und KvA – wie fandet ihr die Klausur?
Tuesday, April 4th 2006, 3:17pm
Quoted
Original von Joachim
Es gilt 2^n = o(2^{2n})
Also folgt nach dem Satz von Savitch SPACE(2^n) \subsetneq SPACE(2^{2n}).
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, April 4th 2006, 3:48pm
Ist a = o(b), so wächst a "echt schwächer" als b, der Unterschied zwischen a und b ist also "mehr" als nur ein konstanter Vorfaktor oder Summand.
Original von Jules
Original von Joachim
Es gilt 2^n = o(2^{2n})
achso, o.k., jetzt verstehe die Definition der Vorlesung auch langsam :-)
Aber was bedeutet nochmal die Notation o (klein o) in Worten? ich meine die praktische Bedeutung.
Ups, ich meinte auch gar nicht den Satz von Savitch, sondern den Raumhierarchiesatz (habe ich ja oben auch schon geschrieben). Der Satz von Savitch hilft hier wie Du richtig sagst, nicht weiter, da es bereits um deterministische Raumklassen geht.
Also folgt nach dem Satz von Savitch SPACE(2^n) \subsetneq SPACE(2^{2n}).
Geht es in dem Satz von Savitch nicht um NSPACE \subset SPACE?
Hätte der Beweis dass lim --> inf = 0 nicht ausgereicht? also ohne den Satz von Savitch zu verwenden?
