48
правок
Изменения
Нет описания правки
=== Утверждение теоремы ===
'''NL''' = '''coNLco-NL'''
=== Доказательство ===
Другими словами это множество всех вершин, достижимых из <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> &nbs;∈ &nbs;'''STNONCON'''.
'''Лемма''': Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
'''for''' v = 1..n; v ≠ s '''do''' //''перебираем все вершины графа, кроме s — это кандидаты на попадание в R<sub>i+1</sub>''
'''for''' u : (u,v) ∈ E '''do''' //''перебираем все ребра, входящие в v''
r++ //''увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата''
'''break'''
Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCON''' на логарифмической памяти.
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>Next</code> (<tex>n - 1</tex> ) раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
<code>
NONCON(G, s, t)
r<sub>n</sub> := 1 //''r<sub>0</sub> = 1''
'''for''' i = 0..(n - 2) '''do''' //''Вычисляем вычисляем r<sub>n-1</sub>''
r<sub>n</sub> := Next(s, i, r<sub>n</sub>, G)
'''REJECT'''
'''else'''
Таким образом показано, что '''STNONCON''' ∈ '''NL'''.
Поскольку '''STNONCON''' ∈ '''coNLCco-NLC''', то получаем, что любую задачу из '''coNLco-NL''' можно свести к задаче из '''NL''', а значит '''coNLco-NL''' ⊂ '''NL'''</tex>.Из соображений симметрии '''NL''' ⊂ '''coNLco-NL''', а значит '''NL''' = '''coNLco-NL'''.
