Gödel Prize - 1993

László Babai, Shlomo Moran, and Shafi Goldwasser, Silvio Micali, 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

Shafi Goldwasser, Silvio Micali, 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.