editor
143
правки
Изменения
→Теорема Иммермана
Введем обозначение <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>.
