Abstract:
The classes of languages accepted by nondeterministic polynomial-time Turing machines (NP machines, in short) that have restricted access to an NP oracle --- the machines can ask k queries to the NP oracle and the answer they receive is the number of queries in the oracle language modulo a number m >= 2 --- are considered. It was shown in~[Han and Thierauf: Structures 1995, pp 206--213] that these classes coincide with an appropriate level of the Boolean hierarchy when m is even or k <= 2m. Here, it is shown that the same holds when m is odd and k >= 2m, and the level of the Boolean hierarchy is given by k+3 - floor{(k+2)/m} + ((k+floor{(k+2)/m}) mod 2). These results are also generalized to the case when the NP machines are replaced by Turing machines accepting languages of the lth level of the Boolean hierarchy.