• DocumentCode
    3357914
  • Title

    PP is closed under truth-table reductions

  • Author

    Fortnow, Lance ; Reingold, Nick

  • Author_Institution
    Chicago Univ., IL, USA
  • fYear
    1991
  • fDate
    30 Jun-3 Jul 1991
  • Firstpage
    13
  • Lastpage
    15
  • Abstract
    R. Beigel et al. (1991) showed that PP is closed under intersection and a variety of special cases of truth-table closure. In the present work, the authors extend the techniques of Beigel et al. to show that PP is closed under general polynomial-time truth-time reductions
  • Keywords
    Turing machines; computational complexity; PP; closed; intersection; polynomial-time; truth-table closure; truth-table reductions; Boolean functions; Polynomials; 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.160239
  • Filename
    160239
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3357914