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

スポンサーリンク

概要

• 論文の詳細を見る

• We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis. For formulas of size at most en, 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.

• 一般社団法人電子情報通信学会の論文
• 2012-06-14

著者

• Seto Kazuhisa

  Graduate School Of Informatics Kyoto University

• Tamaki Suguru

  Graduate School Of Informatics Kyoto University

• Tamaki Suguru

  Graduate School of Informatics, Kyoto University

• Seto Kazuhisa

  Graduate School of Informatics, Kyoto University

関連論文

• New Graph Calculi for Planar Non-3-Colorable Graphs
• The Planar Hajos Calculus for Bounded Degree Graphs
• DS-1-4 Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus
• A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
• A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

スポンサーリンク