An oracle characterization of the counting hierarchy
Jacobo Torán · 1988
Certain properties of the polynomial-time counting hierarchy (CH) introduced by K. Wagner (1986) are investigated. The closure under Boolean operations of the classes in CH is studied, and a characterization of the hierarchy in terms of nondeterministic and probabilistic machines with access to oracles is proved. The concept of lowness is extended to the classes in CH, providing a way to characterize the sets that are low for the class PP using ranking functions. Some other connections are found between ranking functions and low sets for PP, showing that if a class in the hierarchy is Hash P-rankable, then it is low for PP.>