Immerman–Szelepcsényi theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computational complexity theory, the Immerman–Szelepcsényi theorem 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.[1] The result solved the second LBA problem.

In other words, if a nondeterministic machine can solve a problem, it 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.

Logspace hierarchy[edit]

As a corollary, in the same article, Immerman proved that, using descriptive complexity's equality between NL and FO(Transitive Closure), the logarithmic hierarchy, i.e. the languages decided by alternating Turing machine in logarithm space with a bounded number of alternation, is the same class as NL.

See also[edit]

  • Savitch's theorem relates nondeterministic space classes to their deterministic counterparts

Notes[edit]

  1. ^ The standard reference for padding in space complexity (which predates this theorem) is Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences 4: 177–192, MR 0266702 . For a stronger padding argument that applies even to sublogarithmic space complexity classes, see Szepietowski, Andrzej (1994), Turing machines with sublogarithmic space, Lecture Notes in Computer Science 843, Springer-Verlag, Berlin, doi:10.1007/3-540-58355-6, ISBN 3-540-58355-6, MR 1314820 .

References[edit]

External links[edit]