Seinosuke Toda

Seinosuke Toda ( Japanese 戸 田 誠 之 助 , Toda Seinosuke ; born January 15, 1959 ) is a Japanese computer scientist .

Toda received his PhD in 1992 from Kojiro Kobayashi at the Tokyo Institute of Technology ( Counting Classes Are at Least as Hard as the Polynomial Time Hierarchy ). He is a professor at Nihon University .

Toda deals with complexity theory and the design and analysis of algorithms. In 1998 he received the Gödel Prize for his work PP is as Hard as the Polynomial-Time Hierarchy (SIAM Journal on Computing, Volume 20, 1991, pp. 865-877). In it he proved Toda's theorem that the polynomial time hierarchy PH is contained in. It is a machine with polynomzeitliche Sharp P - oracle ( is Sharp P pronounced). A polynomial machine even needs to ask a single Sharp-P question to solve all of the problems in PH. ${\displaystyle P^{\sharp P}}$ ${\displaystyle P^{\sharp P}}$ ${\displaystyle \sharp P}$

Web links

• Homepage (English)

Individual evidence

1. ↑ Seinosuke Toda in the Mathematics Genealogy Project (English)
2. ↑ Faculty of Computer Science Nihon University ( Memento of the original from June 29, 2013 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
3. ↑ Lance Fortnow A simple proof of Toda's theorem , Theory of Computing, Volume 5, 2009, pp. 135-140, pdf