Toda, Seinosuke PP is as hard as the polynomial-time hierarchy. (English) Zbl 0733.68034 SIAM J. Comput. 20, No. 5, 865-877 (1991). In this outstanding paper Toda proves that all sets of the polynomial- time hierarchy PH are \(\leq^ P_ t\)-reducible to a set of PP, i.e. acceptable by a polynomial time-bounded probabilistic Turing machine with two-sided unbounded error probability. As a consequence, it follows that PP\(\subseteq PH\) (\(\oplus P\subseteq PH)\) implies a collaps of PH. Reviewer: C.Meinel (Berlin) Cited in 9 ReviewsCited in 190 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03D15 Complexity of computation (including implicit computational complexity) Keywords:polynomial-time hierarchy; probabilistic Turing machine × Cite Format Result Cite Review PDF Full Text: DOI Link