Satz PATH is NL-vollständig
Einfache Sprache
Satz STCON is NL-vollständig
Beweis: Wir zeigen zunächst das $\mathrm{PATH}\in\mathbf{NL}$, also das es in NLSPACE liegt. Dabei wird ausgehend vom dem Startknoten $s$ nichtdeterministisch eine nächste erreichbarer Knoten gewählt. Dabei wird immer nur der aktuelle Knoten gespeichert. Falls $t$ erreicht wird akzeptiere, falls mehr als $|V|$ Schritte gemacht werden verwerfe. Es wird jeweils nur ein Zähler bzw. ein Pointer in $V$ benutzt, daher ist $\mathrm{PATH}\in\mathbf{NL}$.
Nun fehlt noch die NL-Schwere. Dazu zeigen wir eine Log-Raum-Reduktion von der beliebigen Sprache $A$ in $\mathbf{NL}$ zu $\mathrm{PATH}$. Nach der Definition von NL existiert eine NDTM $\mathcal M_A$ die $A$ in dem Raum $O(\log n)$ entscheidet. Für die Eingabe $w$ konstruieren wird $\langle G, s, t \rangle$, bestehend aus einen Gerichteter Graph $G$, welcher einen Weg von $s$ nach $t$ hat g.d.w. $\mathcal M_A$ $w$ akzeptiert.
$G$ ist wiefolgt aufgebaut. Die Knoten stellen die Konfiguration von $\mathcal M_A$ auf $w$ dar. Für zwei Konfigurationen $c_1$ und $c_2$ ist in $G$ eine Kante $(c_1, c_2)$ g.d.w. $c_2$ eine (mögliche) Folgekonfiguration von $c_1$ ist. $s$ ist die Anfangskonfiguration von $\mathcal M_A$ auf $w$. $\mathcal M_A$ wird so modifiziert, das sie einen einzigen akzeptierende Haltekonfiguration hat. Diese Konfiguration ist dann $t$.
Warum ist das eine Reduktion von $A$ auf $\mathrm{PATH}$? Wenn $\mathcal M_A$ einen Eingabe akzeptiert, dann existiert eine Berechnung die akzeptiert. Diese Folgekonfigurationen bilden eine Pfad von $s$ nach $t$. Umgekehrt gilt, wenn ein Pfad von $s$ nach $t$ in $G$ existiert, es eine akzeptierende Berechnung für $\mathcal M_A$ auf $w$ geben.
Jetzt müssen wir noch einen Logarithmische Platzkomplexität Transduktor angeben der für $w$ $\langle G,s,t\rangle$ ausgibt. $G$ besteht aus einer Liste von Kanten und und einer Liste von Knoten. Bemerke das eine Konstante $c$ existiert so, dass eine beliebige Konfiguration von $\mathcal M_A$ auf $w$ im $c\log n$ großen Raum dargestellt werden kann. Der Transduktor iteriert nun durch alle möglichen Zeichenketten der der Länge $c\log n$. Falls die Zeichenkette ein legale Konfiguration von $\mathcal M_A$ ist wird sie Ausgegeben (kommt also in die Liste von Knoten). Für die Knotenliste iteriert man über alle möglichen Kanten, das Kartesische Produkt der Knoten mich sich selbst. Eine Kante kann ungefähr im $2c\log n$ großen Raum dargestellt werden. Dabei muss der Transduktor für jede Kante nur überprüfen ob aus $c_1$ und den Symbolen auf die die Lese-Schreib-Köpfe zeigen, $c_2$ nach der Transitionsfunktion von $\mathcal M_A$ folgt. Trick is hier das dafür nur die Symbole unter den Lese-Schreib-Köpfen benutzt werden müssen. Es werden nur solche Kanten ausgegeben (also kommen in die Kantenliste), die diesen Test bestehen.