NL-полнота задачи о достижимости в графе

Формулировка задачи

Даны ориентированный граф $G = \langle V, E \rangle$ и две вершины $s, t$ в нем. Необходимо проверить, правда ли, что в графе $G$ существует путь из вершины $s$ в вершину $t$. Эту задачу принято называть $st-connectivity$ или $STCON$.

Теорема

Задача $STCON$ NL-полна.

Доказательство

Для доказательства NL-полноты необходимо показать, что эта задача NL-трудная и принадлежит классу NL.

Доказательство принадлежности задачи STCON классу NL

Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает $O(\log n)$ памяти, где $n$ - размер входа для задачи и за время порядка $O(poly(n))$ решает эту задачу.

Алгоритм:

1. Начиная с вершины $s$ недетерминированно переходит в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)

2. Проверяет, правда ли, что текущая вершина совпадает с $t$. Если это так, возвращает TRUE.

3. Отдельно считает количество пройденных вершин. Как только это число превышает количество вершин в графе, то алгоритм возвращает FALSE, так как посетил некоторую вершину дважды.

Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину $t$ и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают $O(\log n)$ памяти.

Доказательство NL-трудности задачи STCON

Необходимо показать, что любая задача из класса NL сводится к задаче STCON с использованием не более, чем логарифмической памяти.

Необходимо по данной задаче из NL построить тройку $\langle G, s, t \rangle$, решение задачи STCON для которой будет эквивалентно решению данной задачи.

Любая машина Тьюринга, которая принимает некоторый язык L из NL использует не более, чем логарифмическое количество ячеек на рабочей ленте и таким образом возможных мгновенных описаний этой машины Тьюринга $O(poly(n))$. Мгновенным описанием машины Тьюринга считается ее внутреннее состояние, позиция головки на ленте и содержимое рабочей ленты. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в $G$, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга не более, чем некоторое конечное число), ребро в графе $G$. За вершину $s$ принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину $t$.

Очевидно, что для любого слова, из языка L, то есть принимаемого данной машиной Тьюринга, будет существовать путь из $s$ в $t$ в построенном графе $G$. А, если для некоторого слова не из L в $G$ существует путь из $s$ в $t$, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.

Такое построение графа $G$ по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их $O(poly(n))$, потому переменная, перебирающая его занимает $O(\log n)$ памяти), переходы из него и проверка возможности перехода.