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(k)P, are at least as computationally hard as PH (t he polynomial-time hierarchy) in the following sense: for each K of th e counting classes above, every set in K(PH) is polynomial-time random ized many-one reducible to a set in K with two-sided exponentially sma ll error probability. As a consequence of the result, it is seen that all the counting classes above are computationally harder than PH unle ss PH collapses to a finite level. Some other consequences are also sh own.