PP IS AS HARD AS THE POLYNOMIAL-TIME HIERARCHY

In this paper, two interesting complexity classes, PP and +P, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turning reducible to a set in PP, and PH is included in BP . +P. As a consequence of the results, it follows that PP is-contained-or-equal-to PH (or +P is-contained-in-or-equal-to PH) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP.