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 enthalten ist.[3] Dabei ist eine polynomzeitliche Maschine mit Sharp-P-Orakel ( 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.

Einzelnachweise

  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