Satz coPATH is in NL

Einfache Sprache

Def. Satz coPATH is in NL

$\overline{\mathrm{PATH}}\in\mathbf{coNL}$

Beweisidee: Nehme zunächst an wir wissen die Anzahl der Knoten $c$ die von $s$ aus erreichbar sind. Später wird erklärt wie man $c$ berechnet.

Gegeben $G$, $s$, $t$ und $c$ (wobei $m=|V|$) funktioniert die TM $\mathcal M$ mit nichtdeterministische logarithmische Platzkomplexität wie folgt: $\mathcal M$ iteriert über alle Knoten von $G$ und rät nichtdeterministisch ob er von $s$ aus erreichbar ist. Falls für den Knoten $u$ geraten wird, dass er erreichbar ist, versucht $\mathcal M$ diese Vermutung dadurch zu bestätigen, dass es den Pfad von $s$ zu dem Knoten nichtdeterministisch errät. Für jeden erreichbaren Knoten wird dann jeweils ein Zähler inkrementiert. Wenn am Ende der Zähler gleich $c$ ist, wissen wir das wir alle erreichbaren Knoten gesichtet haben und keiner davon $t$ ist. Somit ist $t$ nicht erreichbar von $s$.

Grob sieht die Maschine so aus:

1. Berechne $c$
2. Wähle nichtdeterministisch genau die $c$ Knoten (ohne $t$) die von $s$ erreichbar sind.
3. Überprüfe das jeder Knoten $u$ von $s$ erreichbar ist, indem man nichtdeterministisch den Pfad der Länge $\leq m$ von $s$ nach $u$ findet. Falls der Pfad nicht bei $u$ endet oder in $t$ endet reject
4. Sonst akzeptiere

Wie berechnet man $c$? Dazu folgt eine NL Algorithmus, bei dem mind. eine mögliche Berechnung den korrekten Wert für $c$ hat und alle anderen Berechnungen verwerfen:

Für alle $i\in\mathbb N$ mit $i\leq m$ sei $A_i$ die Menge der Knoten die höchstens $i$ von $s$ entfernt sind. Also ist $A_0=\{s\}$, $A_i\subseteq A_{i+1}$ und $A_m$ beinhaltet alle Knoten die von $s$ erreichbar sind. Sei $c_i := |A_i|$. Wir wollen $c_m = c$. Dazu geben wir eine Prozedur an wie $c_{i+1}$ aus $c_i$ berechnet werden kann:

TODO der algorithmus macht noch keinen Sinn. besonders wie c berechnet wird.

Beweis:

Algorithmus

 1def find_path_nondet(G,s,e,l):
 2	''' Nondeterministically follow a path in G of length at most l from s and reject if it doesn’t end at e.
 3	'''
 4	(V, E) = G
 5	a = s
 6	for x in range(0,l):
 7		TODO
 8
 9def coPath(G, s, t):
10	(V, E) = G
11	cc = 0
12	cn = 1
13	for i in range(0,m-1):
14		cc = cn
15		cn = 1
16		for v in V:
17			if v == s:
18				continue
19			d = 0
20			for u in V:
21				#Nondeterministically skip or perform
22				if (Nondeterministic descision):
23					if find_path_nondet(G, s, v, i):
24						d += 1
25						if (u,v) in E:
26							cn += 1
27							break
28					else:
29						return reject
30			if d != cc:
31				return reject
32	d = 0
33	for u in V:
34		#Nondeterministically skip or perform
35		if (Nondeterministic descision):
36			if find_path_nondet(G, s, u, len(V)):
37				d += 1
38			else:
39				return reject
40	if d == cn:
41		return accept
42	else:
43		return reject

Der Algorithmus braucht nur Speicherplatz für $m = |V|$, u, v, cc, cn, d, i und ein Zeiger auf den Graph. Also hat er nichtdeterministische logarithmische Platzkomplexität.