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