editor
143
правки
Изменения
→Теорема Иммермана
| proof =
Решим задачу <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка <tex>\mathrm{CONN}</tex>.
Чтобы показать, что <tex>\mathrm{NCONN}</tex>\in \mathrm{NL}</tex>, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.
Определим <tex>R_i</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.
