Satz NL teil von P
Einfache Sprache
Def. Satz NL teil von P
Beweis: Aus Satz PATH is NL-vollständig wissen wir, dass jede Sprache in NL logarithmisch platzkomplexitätsreduzierbar auf PATH ist. Nach dem Satz Anzahl der Konfiguration einer ROITM hat eine ROITM, die eine Reduktion ja ist, mit einer Platzkomplexität von $f(n)$ eine Laufzeit von $n2^{O(f(n))}$, da im “worst case” alle möglichen Konfigurationen einmal besucht werden. Da $f(n)\in O(\log n)$ ergibt sich eine Laufzeit von $n2^{O(f(n))} \leq n2^{O(\log n)} \leq O(n^2)$. TODO diese Gleichung stimmt glaub ich nicht. Also gibt es für jede Log-Raum-Reduktion auch eine äquivalente Polynomialzeitreduktion. Also ist jede Sprache polynomial reduzierbar auf $\mathrm{PATH}$. Nach Satz PATH ist in P ist $\mathrm{PATH}\in \mathbf P$. Nun ist jede Sprache in $\mathbf{NL}$ poly. reduzierbar auf $\mathrm{PATH}$ und $\mathrm{PATH}\in\mathbf P$ und daher folgt aus dem Satz Falls B in P und A poly reduzierbar auf B dann A in P, dass $\mathbf{NL}\subseteq\mathbf P$.