TR96-001 Authors: Manindra Agrawal, Richard Beigel, Thomas Thierauf

Publication: 10th January 1996 16:42

Downloads: 3208

Keywords:

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.