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