Warum benötigt man oft eine Platzkonstruktionsfähigkeit in Savitchs Theorem?

Question

Wenn Savitchs berühmtes Theorem angegeben wird, sieht man oft die Anforderung, dass $ s (n) $ space konstruktibel ist (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) $ ist, was aus dem Beweis klar ist. Aber kein Beweis, den ich bisher gesehen habe, verwendet explizit, dass $ s (n) $ Platz aufbaubar ist.

Meine Erklärung: Um die Verfahrensreichweite (oder den Pfad oder wie auch immer Sie es nennen möchten) zu nennen Wir dürfen nicht mehr als $ S (n) $ Space brauchen, um es aufzuschreiben.

Answer 1

Ich glaube, Ihre Erklärung ist korrekt. Die ST-Reach-Unterprogramme erhält $ (s, t, ell) $ als Input und stellt fest, ob $ t $ von $ s $ $ $ ell $ Schritte erreichbar ist oder nicht. $ s $ und $ t $ werden die ersten und endgültigen Konfigurationen sein, und $ ell = 2^{o (s (n))} $, die obere Grenze für die Anzahl verschiedener Konfigurationen.

Um $ ell $ festzulegen, muss man in der Lage sein, $ s (n) $ (oder besser gesagt, $ 2^{o (s (n))} $ zu berechnen. Wenn dieser Vorgang mehr als $ O (s^2 (n)) $ Space benötigt, hat die gesamte Maschine mehr Platz als die zulässigen. Es ist möglich, dass sogar $ o (s^2 (n)) $ zu viel ist, weil der rekursive Aufruf an ST-REACH (gibt es einen anderen möglichen Grund?), Aber ich habe das nicht überprüft.

Answer 2

Dies wird in Dexter Kozens Theorie des Berechnungslehrbuchs in Kapitel 2 gut ausgearbeitet.

Savitch's Theorem (Satz 1 in seinem Papier) sagt: Wenn $ s (n) ge log n $, dann $ text {nspace} (s (n)) subseteq text {dspace} (s (n)^ 2) $. Die Raumkonstruktionsfähigkeit scheint häufig in einem Beweis angenommen zu werden, aber diese Anforderung kann entfernt werden, indem die Suche mit einem festgelegten Platz neu gestartet wird, der mit jedem Versuch erhöht werden darf.

Die Verwirrung entsteht vielleicht, weil die Originales Savitchpapier Es geht weitgehend darum, zu untersuchen, ob $ text {nspace} (s (n)) nicht subseteq text {dspace} (s (n)) $. Aufgrund der folgenden Beobachtung aus dem Papier gibt es daher viel Aufwand für räumlich konstruierbare Funktionen.

Es ist natürlich zu fragen, ob es eine Speicherfunktion gibt, deren deterministische und nicht deterministische Komplexitätsklassen gleich sind. Die Antwort wurde von Manuel Blum gegeben und ist "Ja". Blum zeigte, dass es willkürlich große Speicherfunktionen l (n) gibt, so dass ein Satz innerhalb einer deterministischen Speicherung L (n) akzeptiert wird, wenn und nur wenn er innerhalb einer nichtdeterministischen Speicherung L (n) akzeptiert wird. Diese Funktionen l (n) sind jedoch nicht "gut erzogen" und Satz 3 gilt nicht für sie.

(Hier "gut erzogen" bezieht messbar von Savitch.)