Gödel Prize - 1998

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:

Seinosuke Toda:
"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.


e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.