Изменения
→NL-полнота
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.
| proof =
Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.
Докажем, что <tex>\mathrm{CONN} \in \mathrm{NL}</tex>.
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>\mathrm{CONN}</tex> с использованием не более чем логарифмической памяти.
Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>\mathrm{CONN}</tex> для которой будет эквивалентно решению данной задачи.
Любая машина Тьюринга, которая принимает некоторый язык <tex>\mathrm{L}</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.
}}
==Теорема Иммермана==
