editor
143
правки
Изменения
→Теорема Иммермана
==Теорема Иммермана==
{{ Теорема
| statement = <tex>\mathrm{coNL} = \mathrm{NL = coNL}.</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>.
Определим <tex>R_i</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.
Поскольку <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>, то аналогичным образом <tex>\mathrm{NCONN} \in \mathrm{coNLC}</tex>.
Получаем, что любую задачу из <tex>\mathrm{coNL}</tex> можно свести к задаче из <tex>\mathrm{NL}</tex>, а значит <tex>\mathrm{coNL} \subset \mathrm{NL}</tex>.
Из соображений симметрии <tex>\mathrm{NL} \subset \mathrm{coNL}</tex>, а значит <tex>\mathrm{coNL} = \mathrm{NL}</tex>..
}}
}}
