Seinosuke Toda

Seinosuke Toda (born 1959) is a computer scientist who works at Nihon University in Tokyo and is known for a result in computational complexity theory. He earned his doctorate at the Tokyo Institute of Technology in 1992 under the supervision of Kojiro Kobayashi. His best known result, Toda's theorem, shows that every problem in the polynomial hierarchy can be solved in polynomial time by a Turing reduction to a counting problem. The theorem tied together two parts of complexity theory that had been studied separately, the layered hierarchy of problems defined by alternating quantifiers and the problems that ask how many solutions exist. For this work he received the Godel Prize in 1998. He appears in the Mathematics Atlas as the author of that theorem, which sits in the atlas as part of logic and the foundations of computation.