3-SATを解くあるローカルサーチアルゴリズムの上界の別証明
スポンサーリンク
概要
- 論文の詳細を見る
Dantsin等[3]による3-SATを解く決定性ローカルサーチアルゴリズムの上界の別証明をする.この上界は,nを変数の個数としてO(1.481^n)であるが,現在は,BrueggemannとKern[1]によるO(1.473^n)が最良である.最後に,ここで提案した方法を用いて,O(1.473^n)を達成する可能性について述べる.
- 社団法人電子情報通信学会の論文
- 2004-12-03
著者
関連論文
- 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を解くあるローカルサーチアルゴリズムの上界の別証明