Gödel Prize - 1995

Neil Immerman and Róbert Szelepcsényi

The Gödel prize committee has selected the co-recipients of the Gödel Prize for 1995. The prize is awarded for the following two papers:

Neil Immerman:
"Nondeterministic space is closed under complementation"
SIAM Journal on Computing 17 (1988), 935-938

Róbert Szelepcsényi:
"The method of forced enumeration for nondeterministic automata"
Acta Informatica 26 (1988), 279-284

These two papers, using a subtle yet elementary method, independently proved that nondeterministic space complexity classes are closed under complementation. This surprising result settled a fundamental question in complexity theory that had remained open for more than three decades.