Vorbereitungsblatt 2

t(n)>=n, dann gilt NTIME(t(n)) c= SPACE(t(n))

Beweis: Nur aktuellen Pfad speichern, nicht Baum (dann gilt t(n) als Laufzeit und Speicher)

Sei s(n) >= log(n), dann gilt

SPACE(s(n)) c= TIME(2^O(s(n)))

Beweis:

Laufzeit<=

#Zustände *

#mögl.Kopfpositionen auf Eingabeband *

#mögliche Kopfpositionen auf Arbeitsbändern *

#mögliche Arbeitsinhalte

= z (n+2) (s(n))^k*(a^s(n))^k

Es gibt eine Einband DTM, die bei EIngabe x genau einen Speicherbedarf von f(|x|) hat.

• n^k

• log(n)

• n*log(n)

• 2^n

Es existiert keine raumkonstruierbare Funktion, die Teil von o(log(n)), die nicht bereits konstant ist

Sei s(n) >= log(n), dann gilt

NSPACE(s(n)) c= TIME(2^O(s(n)))