Gödel Prize - 1993László Babai, Shlomo Moran, and Shafi Goldwasser, Silvio Micali, Charles RackoffThe 1993 Gödel Prize was shared by two papers, László Babai and Shlomo Moran: Shafi Goldwasser, Silvio Micali, Charles Rackoff: 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. |
