editor
143
правки
Изменения
Нет описания правки
Алгоритм:
#Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число <tex> O(1) </tex> переменных).#Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает возвращаем TRUE.#Отдельно считаем количество пройденных вершин. Как только это число превышает превысило количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>\mathrm{CONN}</tex> с использованием не более чем логарифмической памяти.
Очевидно, что для любого слова из языка <tex>L</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>L</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа <tex> O(1) </tex> переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходов из него и проверки возможности перехода.
}}
