Toda's theorem is a fundamental result in computational complexity theory, established by Seinosuke Toda in 1991. It states that the entire Polynomial Hierarchy (PH) is contained within P^PP. More formally, PH $\subseteq$ P^PP, where P^PP denotes the class of problems solvable in polynomial time with an oracle for a PP problem. An equivalent and often cited formulation is PH $\subseteq$ P^#P, meaning that every problem in the Polynomial Hierarchy can be reduced to a problem in P with access to an oracle for a #P problem (a counting problem).
Statement of the Theorem: The theorem asserts that for any language L in the Polynomial Hierarchy (PH), there exists a language M in PP such that L is polynomial-time many-one reducible to M. That is, PH is contained in P^PP. Alternatively, PH $\subseteq$ P^#P.
Significance and Implications: Toda's theorem highlights the surprising power of counting classes, particularly PP and #P. It demonstrates that if one can efficiently solve problems involving counting the number of accepting paths of a non-deterministic Turing machine (the essence of #P), then one can solve any problem in the Polynomial Hierarchy.
Key implications include:
- Relationship between PH and Counting Classes: It establishes a strong connection between the alternation-based classes of the Polynomial Hierarchy and probability/counting-based classes.
- Upper Bound for PH: It provides an upper bound for the computational power of the Polynomial Hierarchy. Before Toda's theorem, it was not clear if PH could be contained within a class of similar or lower complexity than EXPTIME (exponential time).
- Potential Collapse of PH: While it doesn't prove that PH collapses to a lower level, it implies that if P=PP (or P=P#P), then PH would collapse to P. This underscores the importance of the P versus PP question.
- Proof Techniques: The proof of Toda's theorem involves intricate techniques, including polynomial-time randomized reductions, amplification using Sipser's theorem, and properties of the permanent (related to Valiant's theorem on #P-completeness). It typically builds up from the lowest levels of PH, showing that NP $\subseteq$ P^PP and co-NP $\subseteq$ P^PP, and then generalizes this using a lifting argument for the entire hierarchy.
Historical Context: Seinosuke Toda published the theorem in his paper "PP is as hard as the Polynomial Hierarchy" in 1991. The result significantly advanced the understanding of the relationships between different complexity classes.
Related Complexity Classes:
- Polynomial Hierarchy (PH): A hierarchy of complexity classes that generalize P and NP, defined by alternating quantifiers (e.g., $\Sigma_k$P, $\Pi_k$P).
- P (Polynomial Time): The class of decision problems solvable by a deterministic Turing machine in polynomial time.
- PP (Probabilistic Polynomial Time): The class of decision problems for which a probabilistic Turing machine exists such that, for 'yes' instances, it accepts with probability greater than 1/2, and for 'no' instances, it accepts with probability less than or equal to 1/2.
- #P (Sharp P): The class of counting problems associated with NP problems, specifically, counting the number of accepting paths of a non-deterministic polynomial-time Turing machine.
- P^PP and P^#P: Classes of problems solvable in polynomial time with access to an oracle for a problem in PP or #P, respectively.