• DocumentCode
    3379811
  • Title

    NP with small advice

  • Author

    Fortnow, Lance ; Klivans, Adam R.

  • Author_Institution
    Dept. of Comput. Sci., Chicago Univ., IL, USA
  • fYear
    2005
  • fDate
    11-15 June 2005
  • Firstpage
    228
  • Lastpage
    234
  • Abstract
    We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP ⊆ NP/log if and only if EXP = P||NP Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in P||NP implies EXP in NP/poly.
  • Keywords
    computational complexity; equivalence classes; NP problem; computational complexity; equivalence; exponential time; nonuniform complexity class; uniform complexity class; Circuits; Computational complexity; Computer science; Polynomials; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-2364-1
  • Type

    conf

  • DOI
    10.1109/CCC.2005.15
  • Filename
    1443088
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3379811