Gödel Prize - 1995
Neil Immerman and Róbert SzelepcsényiThe 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:
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.