Изменения

{{Определение|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>.

=== Доказательство ===Решим задачу '''STNONCON''' (''s-t non connectivity'') на логарифмической памяти и покажем, что '''STNONCON''' ∈ '''NL'''. :<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}</tex> Чтобы показать, что '''STNONCON''' входит в '''NL''', придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, которыйпроверяет достижима ли вершина <tex>t</tex> из <tex>s</tex>. Чтобы показать правильность работы алгоритма требуется: *В случае недостижимости <tex>t</tex> из <tex>s</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>}.

'''Лемма''': Введем обозначение <tex>r_i=|R_i|</tex>.Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> (то есть определять, существует ли путь из <tex>s</tex> в <tex>t</tex> такой длины) и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти(это будет доказано ниже).

Таким образом показано, что <tex>\mathrm{NCONN} \in \mathrm{NL}<code/tex>. Enum(s, i, rПоскольку <subtex>i\mathrm{CONN} \in \mathrm{NLC}</subtex>, G) counter := 0 то аналогичным образом <tex>\mathrm{NCONN} \in \mathrm{coNLC}<//''количество уже найденных и выведенных элементов'' '''for''' v = 1tex>..n '''do''' //''перебираем все вершины графа'' '''continue''' or ''find path'' Получаем, что любую задачу из <tex>\mathrm{coNL}<//''недетерминированно угадываем путь tex> можно свести к задаче из s до v или переходим к следующей вершине'' counter++ '''yield return''' v //''выдаем вершину, до которой угадали путь'' '''if''' counter ≥ r<subtex>i\mathrm{NL}</subtex> '''then''' //''нашли r, а значит <subtex>i\mathrm{coNL} \subset \mathrm{NL}</subtex> вершин, допускаем завершаем работу''. '''ACCEPT''' '''REJECT''' //''не нашли rИз соображений симметрии <subtex>i\mathrm{NL} \subset \mathrm{coNL}</subtex> вершин, не допускаем''а значит <tex>\mathrm{coNL} = \mathrm{NL}</codetex>.}}

{{Лемма| statement = Можно построить недетерминированный алгоритм, который будет допускать <codetex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.| proof = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти. '''Enum'''(<tex>s, i, r_i, G</codetex> ) <tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов '''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа '''continue''' or find path //недетерминированно угадываем путь из s до v или переходим к следующей вершине <tex>counter</tex>++ '''return''' <tex>v</tex> //выдаем вершину, до которой угадали путь '''if''' (<tex>counter \geq r_i</tex>) //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу '''accept''' '''reject''' //не нашли <tex>r_i</tex> вершин, не допускаем '''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.

<code>'''Enum</code> ''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий <code>ACCEPT</code>'''accept''', то происходит допуск.

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

<code> '''Next'''(<tex>s, i, r<sub>ir_i, G</subtex>, G) <tex>r := 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 : (u,v) ∈ \in E </tex> '''do''' //''перебираем все ребра, входящие в <tex>v''</tex> '''if''' (<tex>u </tex> '''in''' ''' Enum'''(<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>'''.

Теперь напишем алгоритм, который будет недетерминированно решать задачу '''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 = 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''' t (<tex>t1</tex> '''in''' ''' Enum'''(<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''' ⊂ '''NLEnum'''необходимо <tex>O(\log |G|)</tex> памяти.Из соображений симметрии '''NL''' ⊂ '''co-NL''', а значит '''NL''' = '''co-NL'''.}}