• DocumentCode
    1683512
  • Title

    Proving SAT does not have small circuits with an application to the two queries problem

  • Author

    Fortnow, Lance ; Pavan, A. ; Sengupta, Samik

  • Author_Institution
    NEC Labs., Princeton, NJ, USA
  • fYear
    2003
  • Firstpage
    347
  • Lastpage
    350
  • Abstract
    We show that if SAT does not have small circuits, then there must exist a small number of formulas such that every small circuit fails to compute satisfiability correctly on at least one of these formulas. We use this result to show that if PNP[1]=PNP[2], then the polynomial-time hierarchy collapses to S2P⊆Σ2p∩Π2p. Even showing that the hierarchy collapsed to Σ2p remained open.
  • Keywords
    circuit complexity; computability; formal languages; probability; set theory; theorem proving; SAT; polynomial-time hierarchy; polynomial-time prover; probability; satisfiability; small circuit; two queries problem; Application software; Circuits; Computational complexity; Computer science; National electric code; Polynomials; Power engineering computing; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-1879-6
  • Type

    conf

  • DOI
    10.1109/CCC.2003.1214433
  • Filename
    1214433