Title :
Bounded query computations
Author :
Wagner, Klaus W.
Author_Institution :
Inst. fuer Inf., Wurzburg Univ., West Germany
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 :
Boolean functions; computational complexity; Boolean hierarchy; NP; bounded query classes; bounded query computations; closure; complexity-bounded computations; oracle; truth-table reducibility; Complexity theory; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5286
