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). Er ist Professor an der Nihon-Universität. 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 P ♯ P {\displaystyle P^{\sharp P}} enthalten ist. Dabei ist P ♯ P {\displaystyle P^{\sharp P}} eine polynomzeitliche Maschine mit Sharp-P-Orakel ( ♯ P {\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.