Изменения

{{Определение|definition=Задача несуществования пути между двумя заданными вершинами в данном графе <tex>\mathrm{NCONN} = Теорема Иммермана ==\{\langle G, s, t \rangle \bigm|</tex> в графе G нет пути из s в t<tex>\}.</tex>}}

{{ Теорема| statement =<tex>\mathrm{coNL} =\mathrm{NL}.</tex>| proof = Утверждение теоремы ===Очевидно, что язык <tex>\mathrm{NCONN}</tex> является дополнением языка <tex>\mathrm{CONN}</tex>.Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL = coNL}</tex>, придумаем недетерминированный алгоритм, использующий <tex>O(\log |G|)</tex> дополнительной памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.

Определим <tex>R_i</tex> === Доказательство ==={<tex>v \bigm|</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.Решим задачу STNONCON на логарифмической памятиДругими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.

:Введем обозначение <tex>r_i=|R_i|</tex>.Если <tex>t \textnotin R_{STNONCONn-1}</tex>, где <tex>n =\{\langle G=\langle |V,E\rangle,s,t\rangle\colon |</tex> нет пути , то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}.</tex>.

:''RМожно построить недетерминированный алгоритм, который будет решать задачу <subtex>i\mathrm{NCONN}</subtex>''&nbsp;=&nbsp;{''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}на <tex>O(\log |G|)</tex> памяти (это будет доказано ниже).

Чтобы показатьТаким образом показано, что STNONCON входит в <tex>\mathrm{NCONN} \in \mathrm{NL}</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>O(\log n)mathrm{NL} \subset \mathrm{coNL}</tex> памяти, которыйа значит <tex>\mathrm{coNL} = \mathrm{NL}</tex>.проверяет достижима ли вершина ''t'' из ''s''.}}

*В Теперь можно построить недетерминированный алгоритм, который будет принимать на вход <tex>r_i</tex> и (в случае недостижимости корректности <tex>r_i</tex>) будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти. ''t'Enumerate' из ''(<tex>s, i, r_i, G</tex>) <tex>counter \leftarrow 0 </tex> //количество уже найденных и выведенных элементов '' недетерминированые выборы приводят алгоритм 'for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа <tex>tryV \leftarrow_? \left\{0, 1\right\}</tex> //недетерминированно угадываем путь из s до v или переходим к единице.следующей вершине '''if''' <tex>tryV = 0</tex> '''continue'''*Если ''t'CheckPath' достижима из ''<tex>(s,v,i)</tex> <tex>counter</tex>++ '''output''' <tex>v</tex> //выдаем вершину, то вне зависимости от недетерминированых выборомдо которой угадали путь '''if''' <tex>counter \neq r_i</tex> //не нашли <tex>r_i</tex> вершин, совершаемых алгоритмомне допускаем '''reject''' '''Enumerate''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, результат нольтак как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.

Определим Теперь, имея '''Enumerate''R', можно по индукции строить <tex>r_i</tex>. Очевидно, что <tex>r_0 = 1<sub/tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. Пусть известно значение <tex>r_i</tex>. Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i+ 1}</subtex>.   ''&nbsp;=&nbsp;'Next'''(<tex>s, i, r_i, G</tex>) <tex>r \leftarrow 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \in R_{i+1}</tex> '''for''' <tex>v = 1..n</tex> : <tex>v\ne s</tex> '''do': существует путь из '' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex> '''for' в ''<tex>u \in V : (u, v) \in E</tex> '' длиной ≤ 'do'i''}. Другими словами это множество всех вершин //перебираем все ребра,входящие в <tex>v</tex>достижимых из '''if''' <tex>u</tex> '''in's'' не более чем за ''i'Enumerate' шагов. Обозначим |''R(<subtex>s, i, r_i, G</tex>) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</subtex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата '''break'''| за '''return'''<tex>r<sub/tex>  Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.Для каждого из них перебираются все ребра, в него входящие.Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i+ 1}</tex>.Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</subtex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enumerate'''.ЗаметимТеперь напишем алгоритм, что если который будет недетерминированно решать задачу <tex>t \notin mathrm{NCONN}</tex> на логарифмической памяти.Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n-1}</tex>.Вычисление <tex>r_{n-1}</tex> происходит путем вызова '''Next''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.   '''NCONN'''(<tex>G, s, где t</tex>) <tex>r_n \leftarrow 1</tex> //<tex>r_0 = 1</tex> '''for''' <tex>i = 0..n- 2</tex> '''do''&nbsp;' //вычисляем <tex>r_{n-1}</tex> <tex>r_n =&nbsp;|</tex> '''Next'V''|(<tex>s, i, r_n, то не существует путь G</tex>) ''s'if' в ''<tex>t</tex> '' в графе 'in''' '''Enumerate'''(<tex>s, n - 1, r_n, G</tex>) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', то есть иначе '''accept''' '''reject''' '''else''' '''accept''' Данный алгоритм использует <mathtex>O(\langle log |G|)</tex> памяти,sтак как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>,tи для вызываемых '''Next''' и '''Enumerate''' необходимо <tex>O(\ranglelog |G|)</mathtex> ∈ STNONCONпамяти.}}