• DocumentCode
    2517744
  • Title

    On the structure of bounded queries to arbitrary NP sets

  • Author

    Chang, Richard

  • Author_Institution
    Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
  • fYear
    1989
  • fDate
    19-22 Jun 1989
  • Firstpage
    250
  • Lastpage
    258
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
  • Conference_Location
    Eugene, OR
  • Print_ISBN
    0-8186-1958-9
  • Type

    conf

  • DOI
    10.1109/SCT.1989.41832
  • Filename
    41832
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2517744