Answers are grounded in this paper and cite their sources.
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 PNP[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 PNP and PNP[O(log n)] in terms of the generalization.
No takes yet. Share an insight, caveat, or question.
Klaus W. Wagner (1990) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: