Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-001 | 10th January 1996 00:00

Modulo Information from Nonadaptive Queries to NP


Authors: Manindra Agrawal, Richard Beigel, Thomas Thierauf
Publication: 10th January 1996 16:42
Downloads: 3208


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.

ISSN 1433-8092 | Imprint