Complexity classes defined by counting quantifiers
Jacobo Torán · Journal of the ACM · 1991
We study the polynomial time counting hierarchy, a hierarchy of complexity classes related to the notion of counting. We investigate some of their structural properties, settling many open questions dealing with oracle characterizations, closure under boolean operations, and relations with other complexity classes. We develop a new combinatorial technique to obtain relativized separations for some of the studied classes, which imply absolute separations for some logarithmic time bounded complexity classes.