Bounded query computations
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 260-277
- https://doi.org/10.1109/sct.1988.5286
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: