editor
143
правки
Изменения
→Теорема Иммермана
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>
| proof =
Решим задачу <tex><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>.
