202
правки
Изменения
Нет описания правки
| statement = <tex>\mathrm{L} \subset \mathrm{NL} \subset \mathrm{P}.</tex>
| proof =
}}
Алгоритм:
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.
Очевидно, что для любого слова из языка <tex>L</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>L</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы переходов из него и проверка проверки возможности перехода.
}}
Введем обозначение <tex>r_i=|R_i|</tex>.
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> (то есть определять, существует ли путь из <tex>s</tex> в <tex>t</tex> такой длины) и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти (это будет доказано ниже).
Таким образом показано, что <tex>\mathrm{NCONN} \in \mathrm{NL}</tex>.
| proof =
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
<tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов
'''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа '''continue''' or find path //недетерминированно угадываем путь из s до v или переходим к следующей вершине <tex>counter</tex>++ '''return'''' <tex>v</tex> //выдаем вершину, до которой угадали путь
'''if''' (<tex>counter \geq r_i</tex>) //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
'''Next'''(<tex>s, i, r_i, G</tex>)
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r s \in R_{i+1}</tex> '''for''' <tex>v = 1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex> '''for''' <tex>u : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex> '''if''' (<tex>u</tex> '''in''' '''Enum'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
'''break'''
'''return''' <tex>r</tex>
'''NCONN'''(<tex>G, s, t</tex>)
<tex>r_n = 1</tex> //<tex>r_0 = 1</tex> '''for''' <tex>i = 0..n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex>
<tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>)
'''if''' (<tex>t1</tex> '''in''' '''Enum'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept'''
[[Категория: Теория сложности]]
[[Категория:Классы сложности]]
