1995 Gödel Prize (original) (raw)

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 byIan Parberry, March 25, 1999.
Last updated Thu Mar 25 10:06:23 CST 1999.