editor
143
правки
Изменения
Нет описания правки
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходов из него и проверки возможности перехода.
}}
{{ Теорема
| statement = <tex>\mathrm{NL} \subseteq \mathrm{P}</tex> (следствие из предыдущей теоремы).
| proof = Необходимо доказать, что <tex>\forall \mathrm{B} \in \mathrm{L}</tex> верно, что <tex>\mathrm{B} \in \mathrm{L}</tex>.
По определению <tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL} </tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>. Следовательно, если <tex>\exists \mathrm{A} \in \mathrm{NLC} : \mathrm{A} \in \mathrm{P}</tex>, то <tex>\forall \mathrm{B}</tex>, сводимого к <tex>\mathrm{A}</tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{P}} \mathrm{A}</tex>, следовательно по теореме <tex>\mathrm{B} \in \mathrm{P}</tex>. Таким образом, если существует язык, принадлежащий <tex>\mathrm{NLC}</tex>, то теорема доказана. Как было показано выше, <tex>\mathrm{CONN}</tex> - такой язык.
}}
