**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"^{ [1] } and was given the 1998 Gödel Prize.

The theorem states that the entire polynomial hierarchy PH is contained in P^{PP}; this implies a closely related statement, that PH is contained in P^{#P}.

#P is the problem of exactly counting the number of solutions to a polynomially-verifiable question (that is, to a question in NP), while loosely speaking, PP is the problem of giving an answer that is correct more than half the time. The class P^{#P} consists of all the problems that can be solved in polynomial time if you have access to instantaneous answers to any counting problem in #P (polynomial time relative to a #P oracle). Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic polynomial-time Turing reduction to a counting problem.^{ [2] }

An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real Turing machines) was proved by Saugata Basu and Thierry Zell in 2009^{ [3] } and a complex analogue of Toda's theorem was proved by Saugata Basu in 2011.^{ [4] }

The proof is broken into two parts.

- First, it is established that

- The proof uses a variation of Valiant–Vazirani theorem. Because contains and is closed under complement, it follows by induction that .

- Second, it is established that

Together, the two parts imply

In computational complexity theory, **bounded-error probabilistic polynomial time** (**BPP**) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances. **BPP** is one of the largest *practical* classes of problems, meaning most problems of interest in **BPP** have efficient probabilistic algorithms that can be run quickly on real modern machines. **BPP** also contains **P**, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

In computational complexity theory, **bounded-error quantum polynomial time** (**BQP**) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class **BPP**.

In computational complexity theory, the class **NC** is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in **NC** if there exist constants *c* and *k* such that it can be solved in time *O*(log^{c} *n*) using *O*(*n*^{k}) parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

In computational complexity theory, **PSPACE** is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

In computational complexity theory, the **time hierarchy theorems** are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with *n*^{2} time but not *n* time.

In computational complexity theory, a **complexity class** is a set of computational problems of related resource-based complexity. The two most common resources considered are time and memory.

In computational complexity theory, **Savitch's theorem**, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function ,

In computational complexity theory, **DSPACE** or **SPACE** is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm.

In computational complexity theory, the complexity class **NTIME( f )** is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time

In computational complexity theory, **P**, also known as **PTIME** or **DTIME**(*n*^{O }), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the **polynomial hierarchy** is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic.

In complexity theory, **PP** is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation **PP** refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.

In computational complexity theory, an **alternating Turing machine** (**ATM**) is a non-deterministic Turing machine (**NTM**) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981.

In computational complexity theory, **NL** is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

In complexity theory, the **Karp–Lipton theorem** states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then

In computational complexity theory, the **Sipser–Lautemann theorem** or **Sipser–Gács–Lautemann theorem** states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ_{2} ∩ Π_{2}.

**Seinosuke Toda** is a computer scientist working at the Nihon University in Tokyo. Toda earned his Ph.D. from the Tokyo Institute of Technology in 1992, under the supervision of Kojiro Kobayashi. He was a recipient of the 1998 Gödel Prize for proving Toda's theorem in computational complexity theory, which states that every problem in the polynomial hierarchy has a polynomial-time Turing reduction to a counting problem.

In computational complexity theory of computer science, the **structural complexity theory** or simply **structural complexity** is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.

In computational complexity theory, **QMA**, which stands for **Quantum Merlin Arthur**, is the quantum analog of the nonprobabilistic complexity class NP or the probabilistic complexity class MA. It is related to BQP in the same way NP is related to P, or MA is related to BPP.

**Quantum complexity theory** is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

- ↑ Toda, Seinosuke (October 1991). "PP is as Hard as the Polynomial-Time Hierarchy".
*SIAM Journal on Computing*.**20**(5): 865–877. CiteSeerX 10.1.1.121.1246 . doi:10.1137/0220053. ISSN 0097-5397. - ↑ 1998 Gödel Prize. Seinosuke Toda
- ↑ Saugata Basu and Thierry Zell (2009);
*Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem*, in*Foundations of Computational Mathematics* - ↑ Saugata Basu (2011);
*A Complex Analogue of Toda's Theorem*, in*Foundations of Computational Mathematics*

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.