Unerreichbarkeitsproblem in Graphen

Einfache Sprache

Def. Unerreichbarkeitsproblem in Graphen

Gegeben ein Gerichteter Graph $G=(V,E)$ und zwei Knoten $s,t\in V$. Existiert kein Gerichteter Kantenzug von $s$ nach $t$? Es ergibt sich folgende Sprache

$$\overline{\mathrm{PATH}} = \overline{\mathrm{STCON}} = \{\langle G, s, t\rangle\mid G \text{ ist ein gerichteter Graph \textbf{ohne} einem gerichtetem Kantenzug von $s$ nach $t$}\}$$

Das Komplement von $\overline{\mathrm{PATH}}$ ist das Erreichbarkeitsproblem in Graphen.

Säzte

• Satz coPATH is in NL
• Satz NL ist gleich coNL Hier wird coPATH verwendet.