48
правок
Изменения
Нет описания правки
то есть <tex><G, s, t> \in \text{STNONCON}</tex>.
'''Лемма''': Можно построить недетерминированный алгоритм, который по данному будет принимать верно заданное <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> и удачно завершаться на логарифмической памяти. Если <tex>r_i</tex> больше истинного размера <tex>R_i</tex>,то алгоритм завершится неудачно;однако если <tex>r_i</tex> меньше истинного размера <tex>R_i</tex>, то алгоритм завершится удачно, но перечислит лишь некое подмножество <tex>R_i</tex>.
<code>
counter++
yield return v //''выдаем вершину, до которой угадали путь''
''if'' counter ≥ r_i ''then'' //''нашли r_i вершин, удачно принимаем и завершаем работу''
ACCEPT
REJECT //''не нашли r_i вершин, отклоняем''
</code>
<tex>Enum</tex> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути. Для угадывания пути достаточно работы необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо помнить лишь хранить текущую вершину пути и пытаться угадывать следующуюугадываемую вершины угадываемого пути. <tex>Enum</tex> является недетерминированой программой недетерминированым алгоритмом и если существует порядок исполнения, чтобы достичь ACCEPT, то он достигается.
Теперь имея <tex>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>.
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2\log |G|</tex>, а для вызываемых Next и Enum необходимо <tex>O(\log |G|)</tex> памяти.
Таким образом показано, что STNONCON ∈ NL. Поскольку STNONCON ∈ coNLC, то получаем, что любую задачу из coNLC можно свести к задаче из NL, а значит coNL<tex>\subset</tex>NL.Из соображений симметрии NL<tex>\subset</tex>coNL, а значит NL = coNL.
