48
правок
Изменения
Нет описания правки
=== Утверждение теоремы ===
<tex>\text{NL } = \text{coNL}</tex>
=== Доказательство ===
Решим задачу <tex>\text{STNONCON }</tex> на логарифмической памяти и покажем, что <tex>\text{STNONCON ∈ } \in \text{NL.}</tex>
:<tex>\text{STNONCON}=\{\langle G=\langle V,E\rangle,s,t\rangle\colon </tex> нет пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G\}.</tex>
Чтобы показать, что <tex>\text{STNONCON }</tex> входит в <tex>\text{NL}</tex>, можно придумать недетерминированый алгоритм, использующий <tex>O(\log n)</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</tex> = <tex>|V|</tex>, то не существует путь <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>,
то есть <tex><G, s, t> \in \text{STNONCON}</tex>.
</code>
<tex>\text{Enum}</tex> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути. Для работы необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую
и следующую угадываемую вершины угадываемого пути.
<tex>\text{Enum}</tex> является недетерминированым алгоритмом и если существует порядок исполнения, чтобы достичь <tex>\text{ACCEPT}</tex>, то он достигается.
Теперь имея <tex>\text{Enum}</tex>, можно индуктивно находить <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>.
<code>
</code>
Данный алгоритм изначально учитывает <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> и еще поочередно значения полученные в результате вызова <tex>\text{Enum}</tex>.
Теперь можно написать алгоритм, который будет недетерминировано решать задачу <tex>\text{STNONCON}</tex> на логарифмической памяти. Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>. Вычисление <tex>r_{n-1}</tex> происходит путем вызова <tex>\text{Next }</tex> <tex>n - 1</tex>, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
<code>
</code>
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2\log |G|</tex>, а для вызываемых <tex>\text{Next}</tex> и <tex>\text{Enum}</tex> необходимо <tex>O(\log |G|)</tex> памяти.
Таким образом показано, что <tex>\text{STNONCON ∈ } \in \text{NL}</tex>. Поскольку <tex>\text{STNONCON ∈ } \in \text{coNLC}</tex>, то получаем, что любую задачу из <tex>\text{coNL }</tex> можно свести к задаче из <tex>\text{NL}</tex>, а значит coNL<tex>\text{coNL} \subset\text{NL}</tex>NL.Из соображений симметрии NL<tex>\text{NL} \subset\text{coNL}</tex>coNL, а значит <tex>\text{NL } = \text{coNL}</tex>.
