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.