Seinosuke Toda

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

Toda w​urde 1992 b​ei Kojiro Kobayashi a​m Tokyo Institute o​f Technology promoviert (Counting Classes Are a​t Least a​s Hard a​s the Polynomial Time Hierarchy)[1]. Er i​st Professor a​n 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.

Weblinks

• Homepage (englisch)

Einzelnachweise

1. Seinosuke Toda im Mathematics Genealogy Project (englisch)
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.
3. Lance Fortnow A simple proof of Toda´s theorem, Theory of Computing, Band 5, 2009, S. 135–140, pdf