Beweis dafür, dass NPSPACE $ subseteq $ exptime

Question

Ich folge "Einführung in die Theorie der Berechnung" von SIPser.

Meine Frage bezieht sich auf die Beziehung verschiedener Klassen, die in vorhanden sind Kapitel 8.2. Die Klasse PSPACE.

$ P subseteq np subseteq pspace = npspace subseteq exptime $

Ich versuche zu verstehen, warum der folgende Teil true $ npspace subseteq exptime $ ist.

Die Erklärung aus dem Lehrbuch folgt:

"Für $ f (x) Geq n $ kann ein TM, der $ f (x) $ Space verwendet Verallgemeinerung des Beweises des Lemma 5.8 auf Seite 194. Eine TM -Berechnung, die eine Haltestelle möglicherweise nicht wiederholt. Daher muss ein TM, der Space $ f (n) $ verwendet (n))} $, so $ npspace subseteq exptime $ "

Ich versuche zu verstehen, warum es wahr ist, warum TM, das $ f (n) $ Space verwendet, rechtzeitig $ f (n) 2^{o (f (n))} $ laufen muss. Versuchen wir, die Formel umzukehren: $ n $ ist die Länge des Eingangs, 2 ist die Größe des Alphabets, $ f (n) $ ist der Speicherplatz, den TM auf dem zweiten Band (Betriebsband) und $ f (n) verwendet Geq n $, aber wie man erklärt, was $ o (f (n)) $ bedeutet. Anscheinend dreht $ 2^{o (f (n))} $ eine Konfiguration aus, so dass $ o (f (n)) $ die Vereinigung der Übergangsfunktion und des Alphabets ausdrücken muss, aber tatsächlich scheint es, als würde ich es falsch verstehen. Die faszinierendste Frage, warum der Übergang von Raum zu Zeit am Ende $ f (n) 2^{o (f (n))} $ für mich sehr vage ist.

Ich werde sehr schätzen, wenn mir jemand diese Beziehung erklären könnte.

Answer 1

Der Ausdruck $ f (n) 2^{o (f (n))} $ ist einfach eine Obergrenze für die Anzahl aller Konfigurationen A $ f (n) $-Space Bounded TM kann haben. So zählen Sie: Wir haben $ | gamma |^{f (n)} = 2^{o (f (n)} $ verschiedene Möglichkeiten, wie man das Arbeitsband füllt, und der Kopf kann auf $ f (sein n) $ verschiedene Positionen. Es gibt auch eine ständige Anzahl von Staaten, in denen wir derzeit sein können, aber dies ist im Exponent im Big-O versteckt.

Wenn ein TM mehr als $ f (n) 2^{o (f (n))} $ Schritte unternimmt, muss es zweimal eine Konfiguration besuchen. Daher fährt es und kann nicht aufhören.