You are not logged in.

61

Tuesday, April 4th 2006, 3:17pm

Hey, hier ist Sinan, konnte mich irgendwie mit meinem Account nicht einloggen

Quoted

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.

Quoted


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?

  • "Joachim" is male
  • "Joachim" started this thread

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

62

Tuesday, April 4th 2006, 3:48pm

Quoted

Original von Jules

Quoted

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.
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.

Quoted

Quoted


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?
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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962