editor
143
правки
Изменения
→Теорема Иммермана
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы из него и проверка возможности перехода.
}}
{{Определение
|definition=Задача несуществования пути между двумя заданными вершинами в данном графе <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G нет пути из s в t<tex>\}.</tex>
}}
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>
| proof =
Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</tex>, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.
