Warum verlangt man in Savitchs Theorem oft Raumkonstruierbarkeit?

Wenn Savitchs berühmter Satz aufgestellt wird, sieht man oft die Anforderung, dass $S(n)$ raumkonstruierbar sein muss (interessanterweise wird es in Wikipedia weggelassen). Meine einfache Frage ist: Warum brauchen wir das? Ich verstehe die Anforderung, dass $S(n)$ in $\Omega(\log n)$ , was aus dem Beweis hervorgeht. Aber kein Beweis, den ich bisher gesehen habe, verwendet explizit, dass $S(n)$ ist.

Meine Erklärung: Um die Prozedur REACH (oder PATH oder wie auch immer Sie sie aufrufen möchten) aufzurufen, muss der letzte Parameter "buchstabiert" werden und damit unsere Raumgrenzen von S (n) nicht für einen Aufruf verlassen werden Wir dürfen nicht mehr als $S(n)$ Speicherplatz benötigen , um es aufzuschreiben.

Ich glaube, deine Erklärung ist richtig. Die Unterroutine st-REACH erhält als Eingabe und ermittelt, ob t über ℓ Schrittevon s aus erreichbar istoder nicht. s und t sind die Anfangs- und Endkonfiguration und ℓ = 2 O ( s ( n ) ) , die Obergrenze für die Anzahl der verschiedenen Konfigurationen.$(s,t,\ell)$$t$$s$$\ell$$s$$t$$\ell=2^{O(s(n))}$

Um zu setzen, muss man in der Lage sein, s ( n ) zu berechnen (oder besser gesagt,$\ell$$s(n)$ ). Wenn dieser Prozess mehr als O ( s 2 ( n ) ) Speicherplatz benötigt, verfügt die gesamte Maschine über mehr Speicherplatz als zulässig. Es ist möglich, dass sogar O ( s 2 ( n ) ) aufgrund des rekursiven Aufrufs von st-REACH zu viel ist (gibt es einen anderen möglichen Grund?), Aber ich habe das nicht überprüft.$2^{O(s(n))}$$O(s^2(n))$$O(s^2(n))$

Dies wird in Dexter Kozens Lehrbuch Theory of Computation in Kapitel 2 ausführlich erläutert.

Savitchs Satz (Satz 1 in seiner Arbeit) sagt: wenn , dann ist NSPACE ( S ( n ) ) ⊆ DSPACE ( S ( n ) 2 ) . Raumkonstruierbarkeit scheint oft in einem Beweis angenommen zu werden, aber diese Anforderung kann beseitigt werden, indem die Suche mit einer festen Raumgrenze neu gestartet wird, die mit jedem Versuch zunehmen darf.$S(n) \ge \log n$$\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$

Die Verwirrung entsteht möglicherweise, weil es im ursprünglichen Savitch-Papier hauptsächlich darum geht, zu untersuchen, ob . Aufgrund der folgenden Beobachtung aus dem Papier wird daher viel Aufwand für raumkonstruierbare Funktionen aufgewendet:$\text{NSPACE}(S(n)) \not\subseteq \text{DSPACE}(S(n))$

Es ist natürlich zu fragen, ob es eine Speicherfunktion gibt, deren deterministische und nichtdeterministische Komplexitätsklassen gleich sind. Die Antwort wurde von Manuel Blum gegeben und lautet "Ja". Blum zeigte, dass es beliebig große Speicherfunktionen L (n) gibt, so dass eine Menge innerhalb des deterministischen Speichers L (n) akzeptiert wird, wenn und nur wenn sie innerhalb des nicht deterministischen Speichers L (n) akzeptiert wird. Diese Funktionen L (n) sind jedoch nicht "brav" und Satz 3 gilt nicht für sie.

(Hier bezieht sich "gut erzogen" auf die raumkonstruierbaren Funktionen, die von Savitch als messbar bezeichnet werden.)