Satz STCON ist in P

Achtung

Satz STCON is NL-vollständig zeigt, dass STCON NL-vollständig ist.

Einfache Sprache

Da eine Lösung nach dem Versuch-und-Irrtum-Prinzip auszuprobieren muss grob abgeschätzt $|V|^{|V|}$ möglichen Kantenzüge betrachten muss, also exponentiell in der Anzahl der Knoten, suchen wir den Kantenzug mithilfe der Breitensuche.

Def. Satz STCON ist in P

Wir definieren den Polynomialzeit Algorithmus $M$ der wie folgt für die Eingabe $\langle G, s, t\rangle$ von STCON funktioniert:

1. Beschrifte $s$ mit $\mathrm{besucht}$.
2. Wiederhole bis keine neuen Knoten mit $\mathrm{besucht}$ beschriftet werden:
3. Durchsuche alle Knoten von $G$ ob folgende Bedingung erfüllt ist: Falls eine Kante von einem beschrifteten Knoten $a$ zu einem unbeschrifteten Knoten $b$ geht, dann beschrifte $b$ mit $\mathrm{besucht}$.
4. Falls $t$ mit $\mathrm{besucht}$ beschriftet ist, accept, sonst rejecet.

Jetzt zeigen wir das $M$ in Polynomialzeit läuft. Schritt 1 und 3 werden offensichtlich nur einmal ausgeführt. Also $O(1)$. Schritt 2 wird höchstens $|V|$ mal ausgeführt, da jedesmal (außer beim letzten Mal) mind. ein neuer Knoten beschriftet werden muss. Also $O(|V|)$. Also ist $\mathrm{STCON}\in O(n)$ und damit in P.