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.

• Homepage (englisch)

1. ↑ Seinosuke Toda im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
2. ↑ Fakultät für Informatik Nihon Universität (Memento des Originals vom 29. Juni 2013 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.chs.nihon-u.ac.jp
3. ↑ Lance Fortnow A simple proof of Toda´s theorem, Theory of Computing, Band 5, 2009, S. 135–140, pdf