Bounded Query Classes

TLDR

Polynomial time machines with restricted access to an NP oracle are studied, where restrictions involve limiting query count or query structure such as truth-table reductions. The authors aim to generalize the Boolean hierarchy to characterize P^NP and P^NP[O(log n)]. By extending the Boolean hierarchy, they provide a framework to characterize these classes. Different restrictions on oracle access yield equivalent or comparable complexity classes, notably allowing multiple characterizations of P^NP[O(log n)].

Abstract

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.