Theoretische Informatik
ETH Theoretische Informatik
ETH Theoretische Informatik
-
- 1 / 15
-
Cartes-fiches
Definiere \(\text{Space}_M(n)\)
\(\text{Space}_M(n) = \max\{\text{Space}_M(x) \mid x \in \Sigma^n\}\)
Definiere \(\text{Time}_M(n)\)
\(\text{Time}_M(n) = \max\{\text{Time}_M(x) \mid x \in \Sigma^n\}\)
Welche Inklusionen halten und sind mehr oder weniger tight?
Welche Inklusionen halten und sind mehr oder weniger tight?
Welche Inklusionen halten und sind einigermassen tight?
Welche Inklusionen halten und sind eingiermassen tight?
Wie wird TIME(t(n)) \subseteq SPACE(t(n)) bewiesen?
Es macht keinen Sinn mehr Speicher zu benötigen als Zeitschritte zu haben, da diese Speicherzellen gar nicht innerhalb der Zeit erreicht werden könnnten.
Wie beweisst man SPACE(s(n)) \subseteq U TIME(c^s(n))?
Ex gilt |InKonf_M(n)| <= c^s(n).
Falls sich zwei innere Konfigurationen wiederholen sollten, macht es keinen Sinn, weiter zu arbeiten.
Nach d * c^s(n) Zeitschritten wurden also alle inneren Konfigurationen besucht und es macht keinen Sinn, länger zu arbeiten als TIME(c^s(n))
Wie beweisst man NTIME(t(n)) \subseteq NSPACE(t(n))?
Sei L \in NTIME(t(n)). Es auf einem berechnungsweg von L, der maximal die Länge d * t(n) hat kann nicht mehr als O(t(n)) Speicher besucht werden, somit gilt Inklusion.
Wie wird NSPACE(s(n)) \subseteq U NTIME(c^s(n)) bewiesen?
Sei L aus NSPACE(s(n).
Eine NTM für L hat maximal |InKonf_M(n)| < c^s(n) innere Konfigurationen, somit macht es keinen Sinn, länger zu arbeiten, da alle nach NTIME(c^s(n)) alle inneren Konfigurationen besucht wurden.
Wie wird TIME(t(n)) \subseteq \NTIME(t(n)) bewiesen?
Jede MTM ist auch eine NTM. Somit gilt Inklusion
Wie wird SPACE(t(n)) \in NSPACE(t(n)) bewiesen?
Jede deterministische TM ist auch eine NTM. Somit gilt Inklusion
Wie wird NTIME(s(n)) \subseteq SPACE(s(n)) bewiesen?
r = obere Schranken möglicher Aktionen
T_M,r = Berechnungsbaum von NTM M, hat max. branching Faktor r.
Jede aktzeptierende Berechnung von NTM M hat maximal die Länge d * s(n).
Wir können kanonisch alle Listen von {(1...r)}^{<=d*s(n)} durchgehen und für jede Liste überprüfen, ob es sich um akzeptierende Berechnung handelt. Eine innere Konfiguration braucht auch max. d2 * s(n) Speicher.
Somit ist berechnung von L \in NTIME(s(n)) in SPACE(s(n)) möglich
Wie wird NSPACE(s(n)) \subseteq U TIME(c^s(n)) bewiesen?
Adjazenzmatrix-Idee!
O.B.d.A. gibt es nur einen akzeptierenden Zustand.
Wir bauen Adjazenzmatrix aller innerer Konfigurationen (c^s(n) * c^s(n) = c^2s(n))
Wir checken, welche Zustände C_i nach C_j verbunden sind (d2 * s(n) pro Paar, also d2 * s(n) * c^2s(n))
Wir finden kürzesten Weg. Geht in O(n^2), n^2 <= c^2s(n), also in O(c^4s(n)) machbar..
Alle Schritte zusammen in O(c^4s(n)) Schritten machbar, somit in TIME(c^s(n))
Wie wird NSPACE(s(n)) \subseteq SPACE(s(n)^2) bewiesen?
Satz von Savitch. Benutze REACHABLE(w, C_start, C_end, m = c^s(n))
Wir überprüfen Rekursiv für jede Konfiguration K ob C_end via K erreicht werden kann:
for each inner Konf K:
if REACHABLE(w, C_start, K, m/2) AND REACHABLE(w, K, C_end, m/2)
return true
Wir müssen also maximal log2(c^s(n)) = s(n) * c1 Zustände speichern. Jeder Zustand hat maximal die grösse d * s(n).
Gesamter Speicherplatzverbrauch somit O(c * s(n)^2)
Somit gilt L \in NSPACE(s(n)) => L \in SPACE(s(n)^2)
Konsequenz: PSPACE = NPSPACE
