On the computational power of PP and (+)P

It follows that neither PP nor (+)P is a subset of or equivalent to PH unless PH collapses to a finite level, strong evidence that both classes are strictly harder than PH.

Abstract

Two complexity classes, PP and (+)P, are compared with PH (the polynomial-time hierarchy). The main results are as follows: (1) every set in PH is reducible in a certain sense to a set in PP, an (2) every set in PH is reducible to a set in (+)P under randomized polynomial-time reducibility with two-sided bounded error probability. It follows from these results that neither PP nor (+)P is a subset of or equivalent to PH unless PH collapses to a finite level. This is strong evidence that both classes are strictly harder than PH.>