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 lth level of the Boolean hierarchy.
As before, these all coincide with levels in the Boolean hierarchy.