Введение
Закрытие недетерминированного пространства при комплементации В теории вычислительной сложности теорема Иммермана Зелепцени утверждает, что классы недетерминированной сложности пространства закрыты при комплементации. Это было доказано независимо Нилом Иммерманом и Робертом Сзелепсени в 1987 году, за что они получили в 1995 году премию Гёделя. В своей общей форме теорема гласит, что NSPACE ((s ((n)) = co NSPACE ((s ((n)) для любой функции s ((n) ≥ log n. Результат эквивалентно указывается как NL = co NL; хотя это особый случай, когда s ((n) = log n, он подразумевает общую теорему стандартным аргументом заполнения. Результат решил вторую проблему LBA. Другими словами, если недетерминированная машина может решить проблему, другая машина с теми же границами ресурсов может решить ее проблему комплемента (с обратными ответами "да" и "нет") в том же асимптотическом пространстве. Никакого аналогичного результата не известно для классов временной сложности, и действительно предполагается, что NP не равен co NP. Принцип, используемый для доказательства теоремы, стал известен как индуктивное подсчет. Он также использовался для доказательства других теорем в вычислительной сложности, включая закрытие LOGCFL при дополнении и существование алгоритмов свободного от ошибок рандомизированного логического пространства для USTCON.
In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE(s(n)) = co NSPACE(s(n)) for any function s(n) ≥ log n. The result is equivalently stated as NL = co NL; although this is the special case when s(n) = log n, it implies the general theorem by a standard padding argument. The result solved the second LBA problem. In other words, if a nondeterministic machine can solve a problem, another machine with the same resource bounds can solve its complement problem (with the yes and no answers reversed) in the same asymptotic amount of space. No similar result is known for the time complexity classes, and indeed it is conjectured that NP is not equal to co NP. The principle used to prove the theorem has become known as inductive counting. It has also been used to prove other theorems in computational complexity, including the closure of LOGCFL under complementation and the existence of error free randomized logspace algorithms for USTCON.
Иерархия логического пространства
В качестве следствия в той же статье Иммерман доказал, что, используя описательное равенство сложности между NL и FO (Transitive Closure), логарифмическая иерархия, т.е. языки, решенные чередующейся машиной Тьюринга в логарифмическом пространстве с ограниченным числом чередований, является тем же классом, что и NL.