1993 Gödel Prize
1993 Gödel Prize
László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran,
and Charles Rackoff
The 1993
Gödel Prize
was shared by two papers,
László Babai and Shlomo Moran,
"Arthur-Merlin games: a randomized proof system and a hierarchy of
complexity classes," Journal of Computer and System Sciences,
36 (1988), 254-276, and
Shafi Goldwasser, Silvio Micali, and Charles Rackoff,
"The knowledge complexity of interactive proof systems,"
SIAM Journal on Computing 18 (1989), 186-208.
These papers introduced the concept of interactive proof systems,
which provides a rich new framework for addressing the question of
what constitutes a mathematical proof. The invention of this framework
has already led to some of the most exciting developments in
complexity theory in recent years, including the discovery of close
connections between interactive proof systems and classical complexity
classes, and the resolution of several major open problems about the
difficulty of finding near-optimal solutions to combinatorial
optimization problems.
Created by
Ian Parberry,
March 24, 1999.
Last updated
Wed Mar 24 17:31:35 CST 1999.