Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy

In this paper, it is shown that many natural counting classes, such as PP, C_ = P, and MODₖ P, are at least as computationally hard as PH (the polynomial-time hierarchy) in the following sense: for each K of the counting classes above, every set in K(PH) is polynomial-time randomized many-one reducible to a set in K with two-sided exponentially small error probability. As a consequence of the result, it is seen that all the counting classes above are computationally harder than PH unless PH collapses to a finite level. Some other consequences are also shown.