期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
