Title :
On the structure of bounded queries to arbitrary NP sets
Author_Institution :
Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
Abstract :
The author examines hierarchies built with arbitrary sets in NP. He determines when these hierarchies are proper and how they relate to the Boolean hierarchy (BH) and the query hierarchy (QH). He studies these questions in the setting of U. Schoning´s high-low sets (see J. Comput. Syst. Sci., vol.27, p.14-28 (1983)). He produces some results about the hierarchies built with arbitrary NP sets. These results are similar to ones already known about BH and QH
Keywords :
computational complexity; Boolean hierarchy; arbitrary NP sets; bounded queries structure; hierarchies; query hierarchy; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41832
