ECCC-Report TR96-001https://eccc.weizmann.ac.il/report/1996/001Comments and Revisions published for TR96-001en-usWed, 10 Jan 1996 16:42:50 +0200
Paper TR96-001
| Modulo Information from Nonadaptive Queries to NP |
Manindra Agrawal,
Richard Beigel,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/1996/001
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.
Wed, 10 Jan 1996 16:42:50 +0200https://eccc.weizmann.ac.il/report/1996/001