The Immerman-Szelepcsenyi Theorem, proved independently by Neil Immerman and Robert Szelepcsenyi in 1987, states that nondeterministic space complexity classes are closed under complementation, so NSPACE of s(n) equals co-NSPACE of s(n) for any function s(n) of at least logarithmic size, and in particular that the class NL equals co-NL. The result resolved the long-standing second LBA problem and introduced the proof technique of inductive counting, and both authors received the 1995 Godel Prize for the work; no comparable result is known for time complexity classes.
Facts
StatementNondeterministic space complexity classes are closed under complementation: NSPACE(s(n)) = co-NSPACE(s(n)) for s(n) at least log n, in particular NL = co-NL. 1 Classification
Statement Form Statement Form Connections
Has Statement Form
In Branch
Source Immerman-Szelepcsenyi theorem, Wikipedia
Principal Result Of
Source Neil Immerman (Wikipedia)
Source Róbert Szelepcsényi (Wikipedia)
Proved By
Source Immerman-Szelepcsenyi theorem, Wikipedia
Source Immerman-Szelepcsenyi theorem, Wikipedia
In the Other Atlases
Credited To
Also in Computing Atlas: credited with this subject.
Also in Computing Atlas: credited with this subject.
Sources
1. Immerman-Szelepcsenyi theorem, Wikipedia
Lead paragraph, statement
nondeterministic space complexity classes are closed under complementation.
Lead paragraph, attribution
was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987.
Proved By: Neil Immerman, Lead sentence
It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize.
Proved By: Róbert Szelepcsényi, Lead sentence
It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize.
- In Branch: Computational Complexity Theory, Lead sentence
In Group: Computability and Complexity Theory, Lead section
In computational complexity theory, the Immerman-Szelepcsényi theorem states
View the SourceNeil Immerman (Wikipedia)
Principal Result Of: Neil Immerman, Lead, Godel PrizeQuote, Principal Result Of: Neil Immerman, Lead, Godel Prize
for proof of what is known as the Immerman-Szelepcsényi theorem
Róbert Szelepcsényi (Wikipedia)
Principal Result Of: Róbert Szelepcsényi, Lead, closure under complementQuote, Principal Result Of: Róbert Szelepcsényi, Lead, closure under complement
(the result known as the Immerman-Szelepcsényi theorem)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.