Изменения

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

== Утверждение Теорема ==Задача <tex> REACH STCON </tex> [[NL-полнота|NL-полна]]. == Доказательство ==Для доказательства [[NL-полнота|NL-полноты]] необходимо показать, что эта задача NL-трудная и принадлежит [[NL|классу NL]]. === Доказательство принадлежности задачи 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> памяти. === Доказательство NL-трудности задачи STCON ===Необходимо показать, что любая задача из класса [[NL]] сводится к задаче STCON с использованием не более, чем логарифмической памяти. Необходимо по данной задаче из [[NL]] построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи STCON для которой будет эквивалентно решению данной задачи. Любая машина Тьюринга, которая принимает некоторый язык L из [[NL]] использует не более, чем логарифмическое количество ячеек на рабочей ленте и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Мгновенным описанием машины Тьюринга считается ее внутреннее состояние, позиция головки на ленте и содержимое рабочей ленты. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга не более, чем некоторое конечное число), ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>. Очевидно, что для любого слова, из языка [[L]], то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А, если для некоторого слова не из [[L]] в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной. Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы из него и проверка возможности перехода. [[Категория:Классы сложности]]