A survey is given of directions, results, and methods in the study of complexity-bounded computations with a restricted number of queries to an oracle. In particular, polynomial-time-bounded computations with an NP oracle are considered. The main topics are: the relationship between the number of adaptive and parallel queries, connections to the closure of NP under polynomial-time truth-table reducibility, the Boolean hierarchy, the power of one more query, sparse oracles versus few queries, and natural complete problems for the most important bounded query classes. >
['Klaus W. Wagner']
Bounded query computations