is a computer scientist working at the

Nihon University , abbreviated as , is a private research university in Japan. Its predecessor, Nihon Law School (currently the Department of Law), was founded by Yamada Akiyoshi, the Minister of Justice, in 1889. It is one of Japan's leading private univers ...

Tokyo Tokyo (; ja, 東京, , ), officially the Tokyo Metropolis ( ja, 東京都, label=none, ), is the capital and List of cities in Japan, largest city of Japan. Formerly known as Edo, its metropolitan area () is the most populous in the world, ...

. Toda earned his Ph.D. from the

Tokyo Institute of Technology is a national research university located in Greater Tokyo Area, Japan. Tokyo Tech is the largest institution for higher education in Japan dedicated to science and technology, one of first five Designated National University and selected a ...

in 1992, under the supervision of Kojiro Kobayashi. He was a recipient of the 1998

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Intere ...

for proving

Toda's theorem Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. Statement The theorem states that the entire poly ...

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, which states that every problem in the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

has a polynomial-time Turing reduction to a counting problem.

Notes

Japanese computer scientists 20th-century Japanese mathematicians 21st-century Japanese mathematicians Theoretical computer scientists Gödel Prize laureates 1959 births Living people Academic staff of Nihon University {{Compu-scientist-stub