×

PP is as hard as the polynomial-time hierarchy. (English) Zbl 0733.68034

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)

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)