48
правок
Изменения
Нет описания правки
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>2\log |G|</tex>, а для вызываемых <tex>Next</tex> и <tex>Enum</tex> необходимо <tex>O(\log |G|)</tex> памяти.
Таким образом показано, что STNONCON ∈ NL. Поскольку STNONCON ∈ coNLC, то получаем, что любую задачу из coNLC coNL можно свести к задаче из NL, а значит coNL<tex>\subset</tex>NL.
Из соображений симметрии NL<tex>\subset</tex>coNL, а значит NL = coNL.
