Изменения

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

{{ Теорема| statement =<tex>\mathrm{coNL} =\mathrm{NL}.</tex>| proof = Утверждение теоремы ==='''[[NL]]''' = '''co-Очевидно, что язык <tex>\mathrm{NCONN}</tex> является дополнением языка <tex>\mathrm{CONN}</tex>.Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL'''}</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</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной ≤ <tex>i</tex>}.Другими словами это множество всех вершинТеперь можно построить недетерминированный алгоритм, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.Обозначим <tex>|R_i|</tex> за который будет принимать на вход <tex>r_i</tex>.Если <tex>t</tex> ∉ <tex>R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> и (в графе <tex>G</tex>, то есть <tex><G, s, t></tex>&nbsp;∈&nbsp;'''STNONCON'''. '''Лемма''': Можно построить недетерминированный алгоритм, который будет допускать случае корректности <tex>r_i</tex> и при этом ) будет перечислять все вершины из <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''' //''перебираем все вершины графа'' '''continue''' or ''find path'' <tex>tryV \leftarrow_? \left\{0, 1\right\}</tex> //''недетерминированно угадываем путь из s до v или переходим к следующей вершине '''if''' <tex>tryV = 0</tex> '''continue''' '''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>.

<code> '''Next'''(<tex>s, i, r<sub>ir_i, G</subtex>, G) <tex>r := \leftarrow 1 </tex> //''r<subtex>r_{i+1}</subtex> хотя бы один, так как s ∈ R<subtex>s \in R_{i+1}</subtex>'' '''for''' <tex>v = 1..n; </tex> : <tex>v ≠ \ne s </tex> '''do''' //''перебираем все вершины графа, кроме <tex>s </tex> — это кандидаты на попадание в R<subtex>R_{i+1}</subtex>'' '''for''' <tex>u \in V : (u,v) ∈ \in E </tex> '''do''' //''перебираем все ребра, входящие в <tex>v''</tex> '''if''' <tex>u </tex> '''in''' Enum'''Enumerate'''(<tex>s, i, r<sub>ir_i, G</subtex>, G) '''then''' //''перечисляем все вершины из R<subtex>iR_i</subtex>, если <tex>u </tex> одна из них, то v ∈ R<subtex>v \in R_{i+1}</subtex>'' <tex>r</tex>++ //''увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата''

'''return''' <tex>r</codetex> 

Алгоритм использует <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''' </codetex> (n - 1) </tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение. 

'''NCONN'''(<codetex> NONCON(G, s, t</tex>) r<subtex>nr_n \leftarrow 1</subtex> := 1 //''r<subtex>0r_0 = 1</subtex> = 1'' '''for''' <tex>i = 0..(n - 2) </tex> '''do''' //''вычисляем r<subtex>r_{n-1}</subtex>'' r<subtex>nr_n = </subtex> := '''Next'''(<tex>s, i, r<sub>nr_n, G</subtex>, G) '''if''' <tex>t </tex> '''in Enum''' '''Enumerate'''(<tex>s, n - 1, r<sub>nr_n, G</subtex>, G) '''then''' //''перечисляем вершины из R<subtex>R_{n-1}</subtex>, если <tex>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>O(\log |G|)</tex>,и для вызываемых <code>Next</code> и <code>Enum</code> необходимо <tex>O(\log |G|)</tex> памяти.

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