48
правок
Изменения
Нет описания правки
:<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:</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> памяти.
<code>
Enum(s, i, r<sub>i</sub>, G)
counter := 0 //''количество уже найденных и выведенных элементов'' '''for''' v = 1..n '''do''' //''перебираем все вершины графа'' '''continue''' or ''find path'' //''недетерминированно угадываем путь из s до v или переходим к следующей вершине'' counter++ '''yield return''' v //''выдаем вершину, до которой угадали путь'' '''if''' counter ≥ r<sub>i</sub> '''then''' //''нашли r<sub>i</sub> вершин, допускаем завершаем работу''
'''ACCEPT'''
'''REJECT''' //''не нашли r<sub>i</sub> вершин, не допускаем''
</code>
<code>
Next(s, i, r<sub>i</sub>, G)
r := 1 //''r<sub>i+1</sub> хотя бы один, так как s ∈ R<sub>i+1</sub>'' '''for''' v = 1..n; v ≠ s '''do''' //''перебираем все вершины графа, кроме s — это кандидаты на попадание в R<sub>i+1</sub>'' '''for''' u : (u,v) ∈ E '''do''' //''перебираем все ребра, входящие в v'' //''перечисляем все вершины из R<sub>i</sub>'' '''if''' u '''in''' Enum(s, i, r<sub>i</sub>, G) '''then''' //''если u одна из них, то v ∈ R<sub>i+1</sub>'' r++ //''увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата'' '''break'''
'''return''' r
</code>
Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.
Для каждого из них перебираются все ребра, в него входящие.
Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</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></tex>''
r<sub>n</sub> := Next(s, i, r<sub>n</sub>, G)
'''REJECT'''
'''else'''
</code>
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2O(\log |G|)</tex>, а и для вызываемых <texcode>\text{Next}</texcode> и <texcode>\text{Enum}</texcode> необходимо <tex>O(\log |G|)</tex> памяти.
Таким образом показано, что '''STNONCON''' ∈ '''NL'''.
Поскольку '''STNONCON''' ∈ '''coNLC''', то получаем, что любую задачу из '''coNL''' можно свести к задаче из '''NL''', а значит '''coNL''' ⊂ '''NL'''</tex>.
Из соображений симметрии '''NL''' ⊂ '''coNL''', а значит '''NL''' = '''coNL'''.
