Manindra Agrawal, Richard Beigel, and Thomas Thierauf

**Abstract: **

A * modular query* consists of asking how many (modulo *m*) of *k*
strings belong to a fixed NP language. Modular queries provide a form
of restricted access to an NP oracle. For each *k* and *m*, we
consider the class of languages accepted by NP machines that ask a
single modular query. Han and Thierauf showed
that these classes coincide with levels of the Boolean hierarchy when
*m* is even or *k < 2m+1*, and they determined the exact levels.
Until now, the remaining case --- odd *m* and large *k* --- looked
quite difficult. We pinpoint the level in the Boolean hierarchy for
the remaining case; thus, these classes coincide with levels of the
Boolean hierarchy for every *k* and *m*.
In addition we characterize the classes obtained by using an NP(*l*)
acceptor in place of an NP acceptor,
where NP(*l*) is the *l*th level of the Boolean hierarchy.
As before, these all coincide with levels in the Boolean hierarchy.