• DocumentCode
    1992190
  • Title

    Collapsing degrees in subexponential time

  • Author

    Joseph, Deborah ; Pruim, Randall ; Young, Paul

  • Author_Institution
    Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
  • fYear
    1994
  • fDate
    28 Jun- 1 Jul 1994
  • Firstpage
    367
  • Lastpage
    382
  • Abstract
    We show that there are subexponential deterministic time classes that have collapsing degrees. In particular, we prove the following: Let t be any effectively superpolynomial time bound. Then there is a set A∈DTIME(t) such that every set B∈degmp(A) is p-isomorphic to A
  • Keywords
    computational complexity; set theory; collapsing degrees; subexponential deterministic time classes; subexponential time; superpolynomial time bound; Computer science; Mathematics; NP-complete problem; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
  • Conference_Location
    Amsterdam
  • Print_ISBN
    0-8186-5670-0
  • Type

    conf

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