Изменения
→Доказательство NL-трудности задачи STCON
=== Доказательство NL-трудности задачи STCON ===
Необходимо показать, что любая задача из класса [[NL]] сводится к задаче STCON с использованием не более, чем логарифмической памяти.
Необходимо по данной задаче из [[NL]] построить тройку <tex> <G, s, t> </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>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
