25
правок
Изменения
Нет описания правки
=== Доказательство принадлежности задачи STCON классу NL ===
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
Алгоритм:
1. Начиная с вершины <tex> s </tex> недетерминированно переходит в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)
2. Проверяет, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.
3. Отдельно считает количество пройденных вершин. Как только это число превышает количество вершин в графе, то алгоритм возвращает FALSE, так как посетил некоторую вершину дважды.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(log n) </tex> памяти.
Так как, если из <tex> s </tex> существует путь в <tex> t </tex>, то он имеет длину не более, чем количество вершин в графе, то алгоритм корректно возвращает FALSE.
=== Доказательство NL-трудности задачи STCON ===
