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.
