• DocumentCode
    3152204
  • Title

    Bounding the complexity of advice functions

  • Author

    Gavaldà, Fucard

  • Author_Institution
    Dept. of Math., California Univ., Santa Barbara, CA, USA
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    249
  • Lastpage
    254
  • Abstract
    It is known that every set A in P/poly has an advice function in PF (Σ2P(A)). It is shown that A also has an advice function in PF(NP(A) ⊕ Σ3P). From this bound, it is shown that separating Δ2P and Σ2 P relative to a set in P/poly is as hard as obtaining the same separation, unrelativized
  • Keywords
    computability; computational complexity; P/poly; advice functions; complexity; Books; Computational modeling; Contracts; Mathematics; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
  • Conference_Location
    Boston, MA
  • Print_ISBN
    0-8186-2955-X
  • Type

    conf

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