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.
Web links
- Homepage (English)
Individual evidence
- ↑ Seinosuke Toda in the Mathematics Genealogy Project (English)
- ↑ 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.
- ↑ Lance Fortnow A simple proof of Toda's theorem , Theory of Computing, Volume 5, 2009, pp. 135-140, pdf
personal data | |
---|---|
SURNAME | Toda, Seinosuke |
ALTERNATIVE NAMES | 戸 田 誠 之 助 (Japanese) |
BRIEF DESCRIPTION | Japanese computer scientist |
DATE OF BIRTH | January 15, 1959 |