Bounded Query Classes 论文

摘要

Polynomial time machines having restricted access to an NP oracle are investigated. Restricted access means that the number of queries to the oracle is restricted or the way in which the queries are made is restricted (e.g., queries made during truth-table reductions). Very different kinds of such restrictions result in the same or comparable complexity classes. In particular, the class $P^{\text{NP}}[O(\log n)]$ can be characterized in very different ways. Furthermore, the Boolean hierarchy is generalized in such a way that it is possible to characterize $P^{\text{NP}}$ and $P^{\text{NP}}[O(\log n)]$ in terms of the generalization.