Wie kann man beweisen, dass USTCONN logarithmischen Platz benötigt?

USTCONN ist das Problem, bei dem entschieden werden muss, ob es in einem Graphen einen Pfad vom Quellscheitelpunkt zum Zielscheitelpunkt gibt, der alle als Teil der Eingabe angegeben wird.$s$$t$$G$

Omer Reingold hat gezeigt, dass USTCONN in L ist (doi: 10.1145 / 1391289.1391291 ). Der Proof konstruiert aus dem Zick-Zack-Produkt einen Expander konstanten Grades . Ein Expander mit konstantem Grad hat einen logarithmischen Durchmesser und man kann dann alle möglichen Pfade unter Verwendung einer konstanten Anzahl von logarithmischen Größenmarkierungen überprüfen.

Das Ergebnis von Reingold gibt eine logarithmische Obergrenze für die Raumkomplexität von USTCONN an, wobei die Raumkomplexität laut der Veröffentlichung "bis zu einem konstanten Faktor" aufgelöst wird. Ich bin gespannt auf die entsprechende Untergrenze, die sonst nirgends in der Zeitung erwähnt wird.

Wie kann man beweisen, dass logarithmischer Raum erforderlich ist, um USTCONN im schlimmsten Fall zu bestimmen?

Bearbeiten: Legen Sie die Eingabedarstellung als Adjazenzmatrix des zugrunde liegenden symmetrischen einfach gerichteten Vertex-Graphen fest, wobei die Zeilen nacheinander aufgelistet werden, um eine Bit-Zeichenfolge zu bilden.$N \times N$$N$$N^2$

Lewis und Papadimitriou zeigten (doi: 10.1016 / 0304-3975 (82) 90058-5 ), dass USTCONN SL-vollständig ist, was mit Reingolds Ergebnis impliziert, dass SL = L ist. Savitch zeigte (doi: 10.1016 / S0022-0000 (70) 80006-X ), dass . Weiter für eine berechenbare Funktion von Stearns, Hartmanis und Lewis (doi: 10.1109 / FOCS .1965.11 ), daher wird für USTCONN mindestens Speicherplatz benötigt. Schließlich sind die üblichen Klassen bekannt, die unter L liegen (zB$\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$$\text{DSPACE}(f(n)) = \text{DSPACE}(1)$$f(n) = o(\log\log n)$$\Omega(\log\log n)$$\text{NC}^1$) sind in Form von Schaltkreisen definiert und sind offensichtlich mit keiner Klasse vergleichbar, die in Form eines begrenzten Raums definiert ist.

Soweit ich sehen kann, lässt dies die (zugegebenermaßen unwahrscheinliche) Möglichkeit offen, dass es einen noch besseren deterministischen Algorithmus gibt, der nur$O((\log n)^\delta)$ aber$\Omega(\log \log n)$ Raum für einige$\delta < 1$ , oder sogar ein nichtdeterministischen Algorithmus zum USTCONN dass Verwendungen$o((\log n)^{1/2})$ Raum.

$\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$$f(n)$$\text{DSPACE}(o(\log n))$

Solange es eine Sprache in L gibt, die logarithmischen Raum benötigt, würde das Zeigen, dass USTCONN für L vollständig ist, unter einer streng "schwächeren" als logspace-Reduktion die gewünschte Untergrenze ergeben.

Ist USTCONN für L unter einer Verkleinerung abgeschlossen, die Speicherplatz benötigt?$o(\log n)$

Immerman zeigte (doi: 10.1137 / 0216051 ), dass eine Version der gerichteten Erreichbarkeit, in der der gewünschte Pfad (aber nicht der Graph selbst) deterministisch ist, für L unter Reduktionen erster Ordnung, die durch AC Schaltungen berechenbar sind, vollständig ist . Dies könnte dann möglicherweise angepasst werden, um zu zeigen, dass USTCONN für L unter FO-Reduktionen vollständig ist. Obwohl AC streng in L enthalten ist, ist AC wieder eine Schaltungsklasse und mir ist keine Möglichkeit bekannt, FO-Reduktionen im sublogarithmischen Raum durchzuführen.$^0$$^0$$^0$

Edit 2015-07-14: Es ist eine interessante philosophische Frage, ob die Speicherplatznutzung eines TM die Größe eines Index in die Eingabe einbeziehen soll (wodurch ein wahlfreier Zugriff auf die Eingabe möglich ist, aber ein zusätzliches Bit benötigt wird, wenn sich die Größe der Eingabe verdoppelt ), oder ob der von einem TM belegte Platz die Anzahl der während einer Berechnung besuchten Worktape-Quadrate ist (wobei davon ausgegangen wird, dass der Eingabebandkopf fest ist und sich nicht ändert, wenn sich die Größe des Eingabebandes verdoppelt). Die ehemalige RAM-Style - Definition gibt sofort ein logspace für untere Grenze jedenBerechnung und Modellierung der aktuellen Computer, die die aktuelle Position in einer Datei als Versatz vom Dateianfang verfolgen. Die letztgenannte klassische Definition geht von einem papierähnlichen Band mit festem Lesekopf aus, das außer dem aktuellen Eingabesymbol nichts über das Band weiß, was Turing möglicherweise in seinem Papier von 1937 beabsichtigt hatte.

Heuristische Argumente wie der Kommentar von Thomas, dass es nicht einmal möglich ist, die Eingabe mit Leerzeichen zu indizieren , scheinen eine moderne RAM-Definition anzunehmen. Stearns / Hartmanis / Lewis verwenden die Definition im TM-Stil, ebenso wie die meisten klassischen Arbeiten in raumgebundenen Berechnungen.$o(\log n)$

Eine logarithmische Untergrenze für USTCONN, die als Adjazenzmatrix dargestellt wird, lässt sich nachweisen, indem man feststellt, dass die unäre Sprache der perfekten Quadrate die Erkennung des logarithmischen Bereichs erfordert (siehe Rūsiņš Freivalds, Modelle der Berechnung, Riemann-Hypothese und Klassische Mathematik , SOFSEM 1998, LNCS 1521, 89) - 106. doi: 10.1007 / 3-540-49477-4_6 ( Preprint)). Dann gilt für USTCONN mit der Adjazenzmatrixdarstellung dieselbe Untergrenze. Dies ist vielleicht zu viel des Betrugs: Normalerweise soll das Durchsetzen des Versprechens in einem Versprechungsproblem im Vergleich zum tatsächlichen Problem einfach sein, aber hier gibt das Durchsetzen des Versprechens, dass die Eingabe ein Graph ist, bereits die Untergrenze. Es wäre also schön, ein Argument für eine untere Grenze des Protokollbereichs für das Versprechungsproblem zu sehen, bei dem die Eingabe garantiert aus der Sprache .$\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$

Die Arbeit Counting Quantifiers, Successor Relations and Logarithmic Space von Kousha Etessami beweist, dass das Problem (das im Wesentlichen prüft, ob ein Scheitelpunkt einem Scheitelpunkt in einem Diagramm vorausgeht , von dem versprochen wird, dass es ein Pfad ist) ) ist unter quantifiziererfreien Projektionen .$\mathbf{ORD}$$s$$t$$G$$\mathsf{L}$

Das Problem kann , um das Problem zu reduzieren , zu sehen , durch Gegeben eine Instanz: -Reduktionen von nur löschen der Rand aus den anderen Kanten und Ausgang als ungerichtete Kanten die Frage ist , ob in dem resultierenden Diagramm verbunden ist. (Hinweis: Die Reduzierung kann wahrscheinlich noch feiner gemacht werden.)$\mathbf{ORD}$$\mathbf{USTCONN}$$\mathsf{FO}$$\langle G,s,t\rangle$$\mathbf{ORD}$$t$$u \rightarrow v$$\{u,v\}$$\mathbf{USTCONN}$$s,t$