editor
143
правки
Изменения
→Теорема Иммермана
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути.
'''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск.
Теперь, имея '''Enum''', можно по индукции находить <tex>r_i</tex>.
Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>.
Пусть известно значение <tex>r_i</tex>.
Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.
'''Next'''(<tex>s, i, r_i, G</tex>)
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r \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 : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex>
'''if''' (<tex>u</tex> '''in''' '''Enum'''(<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>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>.
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова <code>Enum</code>.
Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCON''' на логарифмической памяти.
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>Next</code> (n - 1) раз, при этом каждый раз в качестве <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)
'''if''' t '''in''' Enum(s, n - 1, r<sub>n</sub>, G) '''then''' //''перечисляем вершины из R<sub>n-1</sub>, если t была перечислена, то t достижима и выдаем REJECT, иначе ACCEPT''
'''REJECT'''
'''else'''
'''ACCEPT'''
</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> памяти.
Таким образом показано, что '''STNONCON''' ∈ '''NL'''.
Поскольку '''[[NL-полнота задачи о достижимости в графе|STCON]]''' ∈ '''[[NL-полнота|NLC]]''', то аналогичным образом '''STNONCON''' ∈ '''co-NLC'''.
Получаем, что любую задачу из '''co-NL''' можно свести к задаче из '''NL''', а значит '''co-NL''' ⊂ '''NL'''.
Из соображений симметрии '''NL''' ⊂ '''co-NL''', а значит '''NL''' = '''co-NL'''.
}}
}}
