Изменения

{{Определение|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-t non connectivity'') на логарифмической памяти и покажем, что '''STNONCON''' ∈ '''NL'''</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>.

Чтобы показать, что '''STNONCON''' входит в '''NL''', можно придумать недетерминированый Можно построить недетерминированный алгоритм, использующий который будет решать задачу <tex>\mathrm{NCONN}</tex> на <tex>O(\log |G|)</tex> памяти, которыйпроверяет достижима ли вершина <tex>t</tex> из <tex>s</tex>(это будет доказано ниже).

*В случае недостижимости {{Лемма| statement = Можно построить недетерминированный алгоритм, который будет решать задачу <tex>t\mathrm{NCONN}</tex> из на <tex>sO(\log |G|)</tex> недетерминированные выборы приводят памяти.| proof = Для начала приведем недетерминированный алгоритм к допуску, находящий путь между двумя вершинами с длиной не более заданной.*Если '''CheckPath'''(<tex>s,t,k</tex> достижима из ) <tex>cur \leftarrow s</tex> '''for''' <tex>i = 1..k</tex> '''do''' <tex>v \leftarrow_? \left\{1..n\right\}</tex> '''if''' <tex>(cur, то вне зависимости от недетерминированных выборов, совершаемых алгоритмом, алгоритм не приходит к допуску.v) \notin E</tex> '''reject''' <tex>cur \leftarrow v</tex> '''if''' <tex>cur \ne t</tex> '''reject'''

Определим <tex>R_i = \{v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\le 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></tex> ∈ '''STNONCON'''. '''Лемма''': Можно построить недетерминированный алгоритм, который будет принимать верно заданное случае корректности <tex>r_i</tex> (AAAA) и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.  '''Enumerate'''(<codetex> Enum(s, i, r<sub>ir_i, G</subtex>, G) <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''' or ''find path'CheckPath' //''недетерминированно угадываем путь из <tex>(s до ,v или переходим к следующей вершине'',i)</tex> <tex>counter</tex>++ '''yield returnoutput''' <tex>v </tex> //''выдаем вершину, до которой угадали путь'' '''if''' counter ≥ r<subtex>icounter \neq r_i</subtex> '''then''' //''не нашли r<subtex>ir_i</subtex> вершин, не допускаем завершаем работу'' '''ACCEPTreject''' '''REJECT'Enumerate'' //''не нашли r_i вершин, не допускаем''</code> <code>Enum</code> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.

Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. <code>Enum</code> является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий <code>ACCEPT</code>, то происходит допуск.

Теперь , имея <code>Enum</code>'''Enumerate''', можно индуктивно находить по индукции строить <tex>r_i</tex>.

'''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''' //перебираем все ребра, входящие в <tex>v</tex> '''if''' <tex>u</tex> '''in''' '''Enumerate'''(<tex>s, i, r_i, G</tex>) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата '''break''' '''return''' <tex>r</tex>  Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.

Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова <code>Enum</code>'''Enumerate'''.

Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCON''' <tex>\mathrm{NCONN}</tex> на логарифмической памяти.

Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>'''Next</code> ''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.

<code> NONCON'''NCONN'''(<tex>G, s, t</tex>) r<subtex>nr_n \leftarrow 1</subtex> := 1 //''r<subtex>0r_0 = 1</subtex>'' '''for''' <tex>i = 0..(n - 2) </tex> '''do''' //''Вычисляем rвычисляем <subtex>r_{n-1</sub>}</tex>'' r<subtex>nr_n = </subtex> := '''Next'''(<tex>s, i, r<sub>nr_n, G</subtex>, G) //''Перечисляем вершины из R'if''' <subtex>n-1t</subtex>'' 'in''' '''ifEnumerate''' t in Enum(<tex>s, n - 1, rr_n, G</tex>) //перечисляем вершины из <subtex>R_{n-1}</subtex>, G) '''then''' если <tex>t<//''Если t tex> была перечислена, то <tex>t </tex> достижима и выдаем REJECT'''reject''', иначе ACCEPT'''accept''' '''REJECTreject'''

'''ACCEPTaccept'''</code> Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2\log |G|</tex>, а для вызываемых <tex>\text{Next}</tex> и <tex>\text{Enum}</tex> необходимо <tex>O(\log |G|)</tex> памяти.

Таким образом показаноДанный алгоритм использует <tex>O(\log |G|)</tex> памяти, что '''STNONCON''' ∈ '''NL'''.Поскольку '''STNONCON''' ∈ '''coNLC''', то получаемтак как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, что любую задачу из и для вызываемых '''coNLNext''' можно свести к задаче из и '''NL''', а значит '''coNL''' ⊂ '''NLEnumerate'''необходимо <tex>O(\log |G|)</tex>памяти.Из соображений симметрии '''NL''' ⊂ '''coNL''', а значит '''NL''' = '''coNL'''.}}