Structural properties of the counting hierarchies

We study three different hierarchies related to the notion of counting: the polynomial time counting hierarchy, the hierarchy of counting functions, and the logarithmic time counting hierarchy. We investigate the connections between these hierarchies and study some of their structural properties, settling many open questions dealing with oracle characterizations, closure under boolean operations, lowness, complete problems, succint representations, and relations with other complexity classes. We develop a new combinatorial technique to obtain relativized separations, and we obtain also absolute separations for some of the studied classes