Hey, hier ist Sinan, konnte mich irgendwie mit meinem Account nicht einloggen
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.
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?