1995 Gödel Prize
1995 Gödel Prize
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 and
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.
Created by
Ian Parberry,
March 25, 1999.
Last updated
Thu Mar 25 10:06:23 CST 1999.