Immerman-Szelepcsenyi Theorem

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.