The counting hierarchy (Wagner 1986) is the union of complexity classes obtained by repeatedly allowing polynomial-time probabilistic
machines to query the preceding level as an oracle. Write
for decision problems whose yes-instances have
acceptance probability greater than 
and whose no-instances have acceptance probability
at most 
, using fair random bits and polynomial
running time. The levels are
 |
Membership in a level uses a fixed oracle language and a fixed uniform machine. Every fixed level is contained in polynomial space.
