• DocumentCode
    2653253
  • Title

    A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

  • Author

    Seto, Kazuhisa ; Tamaki, Suguru

  • Author_Institution
    Grad. Sch. of Inf., Kyoto Univ., Kyoto, Japan
  • fYear
    2012
  • fDate
    26-29 June 2012
  • Firstpage
    107
  • Lastpage
    116
  • Abstract
    We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis. For formulas of size at most cn, our algorithm runs in time 2(1-μc)n for some constant μc >; 0. As a byproduct of the running time analysis of our algorithm, we get strong average-case hardness of affine extractors for linear-sized formulas over the full binary basis.
  • Keywords
    Boolean algebra; computability; computational complexity; Boolean formulas; affine extractors; average-case hardness; exponential time algorithm; full binary basis; linear-sized formulas; satisfiability algorithm; Algorithm design and analysis; Educational institutions; Encoding; Informatics; Logic gates; Polynomials; Reactive power; average-case hardness; exact algorithm; formula; parity gate; satisfiability;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on
  • Conference_Location
    Porto
  • ISSN
    1093-0159
  • Print_ISBN
    978-1-4673-1663-7
  • Type

    conf

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