1998 Gödel Prize

1998 Gödel Prize

Seinosuke Toda

The 1998 Gödel Prize for outstanding journal article in the area of theoretical computer science will be awarded to Seinosuke Toda for his paper "PP is as Hard as the Polynomial-Time Hierarchy," SIAM Journal on Computing 20 (1991), 865-877.

In the remarkable paper "PP is as hard as the polynomial- time hierarchy" Seinosuke Toda showed that two fundamental and much studied computational concepts had a deep and unexpected relationship. The first is that of alternation of quantifiers - if one alternates existential and universal quantifiers for polynomial time recognizable functions one obtains the polynomial time hierarchy. The second concept is that of counting the exact number of solutions to a problem where a candidate solution is polynomial time recognizable. Toda's astonishing result is that the latter notion subsumes the former - for any problem in the polynomial hierarchy there is a deterministic polynomial time reduction to counting. This discovery is one of the most striking and tantalizing results in complexity theory. It continues to serve as an inspiration to those seeking to understand more fully the relationships among the fundamental concepts in computer science.


Created by Ian Parberry, March 25, 1999.
Last updated Thu Mar 25 10:06:23 CST 1999.