Seinosuke Toda

Seinosuke Toda (jap. 戸田 誠之助, Toda Seinosuke; * 15. Januar 1959) ist ein japanischer Informatiker.

Toda wurde 1992 bei Kojiro Kobayashi am Tokyo Institute of Technology promoviert (Counting Classes Are at Least as Hard as the Polynomial Time Hierarchy)^[1]. Er ist Professor an der Nihon-Universität.^[2]

Toda befasst sich mit Komplexitätstheorie und Entwurf und Analyse von Algorithmen. 1998 erhielt er den Gödel-Preis für seine Arbeit PP is as Hard as the Polynomial-Time Hierarchy (SIAM Journal on Computing, Band 20, 1991, S. 865–877). Darin bewies er den Satz von Toda, dass die Polynomialzeithierarchie PH in ${\displaystyle P^{\sharp P}}$ enthalten ist.^[3] Dabei ist ${\displaystyle P^{\sharp P}}$ eine polynomzeitliche Maschine mit Sharp-P-Orakel (${\displaystyle \sharp P}$ wird Sharp-P ausgesprochen). Eine polynomzeitliche Maschine braucht sogar nur eine einzige Sharp-P Frage zu stellen, um alle Probleme in PH zu lösen.