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.