• DocumentCode
    3358873
  • Title

    Bounded queries in recursion theory: a survey

  • Author

    Gasarch, William

  • Author_Institution
    Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA
  • fYear
    1991
  • fDate
    30 Jun-3 Jul 1991
  • Firstpage
    62
  • Lastpage
    78
  • Abstract
    The author surveys much of the work that has been done on the following two questions: (1) What functions can one compute with m queries to A? and (2) Are there functions that can be computed with m queries to A that cannot be computed with m-1 queries to A? To any set X? The framework is recursion-theoretic; the computations have no time or space bound
  • Keywords
    computational complexity; bounded queries; recursion theory; Complexity theory; Computer science; Concurrent computing; Educational institutions; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
  • Conference_Location
    Chicago, IL
  • Print_ISBN
    0-8186-2255-5
  • Type

    conf

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