• DocumentCode
    2200466
  • Title

    With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets

  • Author

    Fu, Bin

  • Author_Institution
    Dept. of Comput. Sci., Beijing Comput. Inst., China
  • fYear
    1993
  • fDate
    18-21 May 1993
  • Firstpage
    185
  • Lastpage
    191
  • Abstract
    The lower bounds of queries required by the polynomial-time Turing reductions from exponential time classes to the sets of small density are investigated. Results for complexity classes E=DTIME(2linear ) and EXP-DTIME(2poly) are shown
  • Keywords
    Turing machines; computational complexity; EXP; exponential time classes; polynomial time Turing reducible; quasi-linear queries; sparse sets; Circuits; Cognitive science; Computational modeling; Computer science; History; Laboratories; Polynomials; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
  • Conference_Location
    San Diego, CA
  • Print_ISBN
    0-8186-4070-7
  • Type

    conf

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