Immerman–Szelepcsényi theorem

The theorem states that every nondeterministic space complexity class is closed under complement. Its landmark consequence is NL = co-NL.

Configuration graph: A directed graph whose vertices represent machine configurations and whose edges represent legal transitions. A space-bounded computation becomes reachability between its start and accepting configurations.
Neil Immerman: An American theoretical computer scientist known for work in descriptive and computational complexity. He independently proved closure of nondeterministic space under complement.
co-NL: The class of complements of languages in nondeterministic logarithmic space. The theorem proves that every problem in co-NL is also in NL.
Nondeterministic Turing machine: A computational model that can branch into multiple possible transitions at each step. Acceptance means at least one branch succeeds; complementing that condition is the theorem’s challenge.
Reachability problem: The problem of deciding whether a path connects two vertices in a graph. The theorem reduces complementing nondeterministic computation to counting reachable configurations.
Róbert Szelepcsényi: A Hungarian theoretical computer scientist known for proving nondeterministic space classes are closed under complement. His independent proof supplied the theorem’s second name.
NL-completeness: Completeness under suitable reductions for the class of nondeterministic logarithmic-space problems. Closure under complement lets complement versions of NL problems remain within NL.
Complement of a language: The set of strings over an alphabet that are not members of a given language. Closure under complement asks whether negating membership preserves the complexity class.
Inductive counting: A method that counts objects in successive layers by verifying each count with bounded resources. It certifies the number of configurations reachable within each path length.
STOC 1987: The 1987 ACM Symposium on Theory of Computing, a major conference in theoretical computer science. Immerman presented his result there, helping establish the theorem’s historical context.

Linked from 1 page