Изменения

<tex>\text{'''NL} ''' = \text{'''coNL}</tex>'''(ffff)

Решим задачу <tex>\text{'''STNONCON}</tex> ''' (''s-t non connectivity'') на логарифмической памяти и покажем, что <tex>\text{'''STNONCON} \in \text{''' ∈ '''NL}</tex>'''.

Чтобы показать, что <tex>\text{'''STNONCON}</tex> ''' входит в <tex>\text{'''NL}</tex>''', можно придумать недетерминированый алгоритм, использующий <tex>O(\log n|G|)</tex> памяти, который

*В случае недостижимости <tex>t</tex> из <tex>s</tex> недетерминированые недетерминированные выборы приводят алгоритм к допуску.*Если <tex>t</tex> достижима из <tex>s</tex>, то вне зависимости от недетерминированых недетерминированных выборов, совершаемых алгоритмом, алгоритм не приходит к допуску.

то есть <tex><G, s, t> \in \text{STNONCON}</tex>∈ '''STNONCON'''.

'''Лемма''': Можно построить недетерминированный алгоритм, который будет принимать верно заданное <tex>r_i</tex> (AAAA) и при этом будет перечислять все вершины из <tex>R_i</tex> на логарифмической <tex>O(\log |G|)</tex> памяти.

Enum(s, i, r<texsub>r_ii</texsub>, G)

'''continue''' or ''find path'' //''недетерминировано выбираем переходить недетерминированно угадываем путь из s до v или переходим к следующей вершине или угадываем путь до данной''

'''if''' counter ≥ r<texsub>\ge r_ii</texsub> '''then''' //''нашли r<texsub>r_ii</texsub> вершин, принимаем и допускаем завершаем работу''

'''REJECT''' //''не нашли r<texsub>r_ii</texsub> вершин, отклоняемне допускаем''

Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины путииз <tex>s</tex> в <tex>v</tex>. Для работы угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущуюи следующую угадываемую вершины угадываемого пути. <texcode>\text{Enum}</texcode> является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий <texcode>\text{ACCEPT}</texcode>, то происходит допуск.

Теперь имея <texcode>\text{Enum}</texcode>, можно индуктивно находить <tex>r_i</tex>. Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину - (ааааа) — <tex>s</tex>.

Next(s, i, r<texsub>r_ii</texsub>, G) r := 1 //''r<texsub>r_{i+1}</texsub> хотя бы один, так как s ∈ R<texsub>s R_{i + 1}</texsub>'' (∈AAAAAAAA) '''for''' v = 1..n; <tex>v \neq ≠ s</tex> '''do''' //''перебираем все вершины графа, кроме s -- — это кандидаты на попадание в R<texsub>R_{i + 1}</texsub>'' '''for''' u : (u,v)<tex>\in</tex>∈ E '''do''' //''перебираем все ребра, входящие в v'' //''перечисляем все вершины из R<texsub>R_ii</texsub>'' '''if''' u '''in ''' Enum(s, i, r<texsub>r_ii</texsub>, G) '''then''' //''если u одна из них, то v ∈ R<texsub>v \in R_{i + 1}</texsub>''

Данный алгоритм изначально учитывает <tex>s</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> и еще поочередно значения полученные в результате вызова <texcode>\text{Enum}</texcode>.

Теперь можно написать напишем алгоритм, который будет недетерминировано недетерминированно решать задачу <tex>\text{'''STNONCON}</tex> ''' на логарифмической памяти. Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>. Вычисление <tex>r_{n-1}</tex> происходит путем вызова <texcode>\text{Next}</texcode> <tex>n - 1</tex>раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.

r<texsub>r_nn</texsub> := 1 //''r<texsub>r_00</texsub>'' '''for''' i = 0..(n - 2) '''do''' //''Вычисляем r<texsub>r_{n - 1}</sub></tex>'' r<texsub>r_nn</texsub> := Next(s, i, r<texsub>r_nn</texsub>, G) //''Перечисляем вершины из R<texsub>R_{n - 1}</texsub>'' '''if''' t in Enum(s, n - 1, r<texsub>r_nn</texsub>, G) '''then''' //''Если t была перечислена , то t достижима и выдаем REJECT, иначе ACCEPT''

Таким образом показано, что <tex>\text{'''STNONCON} \in \text{''' ∈ '''NL}</tex>'''. Поскольку <tex>\text{'''STNONCON} \in \text{''' ∈ '''coNLC}</tex>''', то получаем, что любую задачу из <tex>\text{'''coNL}</tex> ''' можно свести к задаче из <tex>\text{'''NL}</tex>''', а значит <tex>\text{'''coNL} \subset \text{''' ⊂ '''NL}'''</tex>.Из соображений симметрии <tex>\text{'''NL} \subset \text{''' ⊂ '''coNL}</tex>''', а значит <tex>\text{'''NL} ''' = \text{'''coNL}</tex>'''.