SATを解くO^^〜(1.234^m)時間決定性アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
一般の充足可能問題(節の個数が限定されないSAT)を解くHirschによる決定性アルゴリズムの上界を改良した. Hirschのアルゴリズムを更に詳細に解析することによって, Hirschによって示された上界O^^〜(1.239^m)をO^^〜(1.234^m)に改良した.
- 社団法人電子情報通信学会の論文
- 2005-12-15
著者
関連論文
- On NK-Community Problem (Theoretical Computer Science and its Applications)
- 25pQK-12 正解が埋め込まれたグラフ等分割問題の統計力学的解析(ネットワーク一般・情報統計力学,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- MAX-2SAT問題の平均時間計算量の解析
- MAX-2SAT問題の平均時間計算量の解析
- A Message Passing Algorithm for MAX2SAT(New Trends in Theory of Computation and Algorithm)
- On generating instances for MAX2SAT with optimal solutions (Evolutionary Advancement in Fundamental Theories of Computer Science)
- MAX2SATの解答付き例題生成アルゴリズムの提案
- SATを解くO^^〜(1.234^m)時間決定性アルゴリズム
- 3-SATを解くあるローカルサーチアルゴリズムの上界の別証明
- 3-SATを解くあるローカルサーチアルゴリズムの上界の別証明