Immerman and Szelepcsényi: nondeterministic space is closed under complement

What is recorded here?

Immerman and Szelepcsényi independently established that nondeterministic space at least logarithmic in input length is closed under complement, including NL = co-NL and complement closure of context-sensitive languages. A nondeterministic computation accepts when at least one possible branch accepts. Merely swapping accept and reject therefore cannot certify that no accepting branch exists: another branch may reject even when the answer is yes. Inductive counting overcomes this obstacle. In the inspected Immerman argument, the machine repeatedly certifies the exact number of configurations reachable within a growing number of steps. A complete count forces any successful enumeration to include every reachable configuration, so it can establish that none is accepting while reusing small workspace. The result shows that these space-bounded classes admit equally space-bounded recognition of their complements. It settles the complement question for context-sensitive languages without equating nondeterministic and deterministic computation, or solving P versus NP. Immerman and Szelepcsényi published independent papers; this record represents the shared closure theorem once, with separate attribution. The scientific body inspected is an author-hosted seven-page Immerman version, not a byte-matched reproduction of either journal article.

Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.

Scientific scope

The theorem concerns nondeterministic space at least logarithmic under the stated machine/space conventions, including NL=coNL. It does not imply NP=coNP or L=NL. Verified reachable counts and finite configuration encoding are essential; flipping nondeterministic outcomes is unsound. Independent Szelepcsényi credit is source-supported, but his complete proof has not been independently reconstructed here.

Read the original work

• Immerman: Nondeterministic Space is Closed Under Complementation — author version
• Immerman — 1988 SIAM publisher metadata
• Szelepcsényi — 1988 Acta Informatica publisher identity and abstract
• ACM-SIGACT: original 1995 Gödel Prize independent-proof citation

This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.

People and systems

Neil Immerman; Róbert Szelepcsényi

Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.