グラフの色ぬり分け問題からSATへの効率の良い変換方法とその評価
スポンサーリンク
概要
- 論文の詳細を見る
NP完全問題は,問題のサイズに対して多項式時間で解くアルゴリズムが知られていない問題の代表例である.これらの問題は多項式程度の違いを無視すれば,同じ計算時間で解けるという点で,同じクラスに属する.即ち,ある問題を多項式時間で別の問題に変換することができる.これらの変換は,問題のNP完全性を証明するのに用いられてきた.多項式時間であればどのような変換であってもかまわないという大雑把なものであったが,問題を変換して解くという実用性を考えれば,変換の効率を良くすることが大切になってくる.例えば,CNF論理式の充足可能性問題(SAT)に対する効率の良いアルゴリズムに局所探索法と呼ばれるものがある.ハミルトン閉路問題をSATに変換し,局所探索法で解く場合には,変換によって得られる論理式のの変数の数によって計算時間に格段の差があることが分かっている.本研究では,別のNP完全問題である,グラフの頂点彩色可能性問題をSATに変換する方法を考察してみた.本稿では,まず,頂点数N,色数Kとして,N log K変数での比較的自然な変換の方法を述べる.次に,N logよりも少ない変数の数で変換する方法を2つ述べる.1つは,グラフ中に枝が少ないときに有効であり.もう1つは,枝の数が多いときに有効であることが分かった.NP完全問題は手に負えないという形で統一的に論じられることが多く,個々の問題の難しさの違いはあまり論じられていないようにみえる.本論文で述べている手法,つまりNP完全問題PをSATに変換するのに何変数必要であるかは,ある意味でPの難しさのメジャーになりうると考えられる.計算ステップ数,領滅量等の従来のメジャーとの大きな違いは,定数係数の違い,あるいは定数の差さえも十分に議論でき,それが重要とみなされる点である.
- 1993-09-27
著者
関連論文
- NP完全集合によるco-NP完全集合の近似
- 充足可能性問題に対する計数法の項の選択による高速化
- グラフの色ぬり分け問題からSATへの効率の良い変換方法とその評価
- RS型ベクトル機械上での幾つかの具体的問題に対するアルゴリズム
- 「高度応用のための情報ベースモデルとその実現技術」を目指して (メディア統合および環境統合のための高機能データベースシステム、および一般)
- ブロック同期方式による並列アルゴリズムの記述とそのプログラム化
- ブロック同期に基づく並列アルゴリズムアニメーションシステム
- 充足可能性問題に対する計数法の変数の選択による改良
- 正則グラフに対する密な部分グラフ問題
- ファンイン制限つき組合せ論理回路に対する完全な等価変換規則集合
- 素子制限のある論理回路を等価変換するための基本操作集合について
- ランダムベンチマーク例題による論理最適化システムの評価
- ランダムベンチマーク例題による論理最適化システムの評価
- 論理最適化アルゴリズム評価のためのテスト例題のランダム生成
- 論理最適化アルゴリズム評価のためのテスト例題のランダム生成
- 論理回路簡単化問題に対する例題生成
- 一切の情報を漏らさずプログラムの正当性を証明する方法
- 並列計算用に拡張したTMの時間計算量の階層
- チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)
- テープ記号数を制限した領域限定TMの階層について
- CNF論理式に対する局所探索法の項の追加による改良
- リテラルの出現回数を制限した充足不能な3CNF式
- リテラル出現回数が2回の充足不能な3SAT式
- 確率的手法によるCRCW PRAM間の模倣について
- メッシュバス上での最小全域木アルゴリズム
- グラフの最小全域木を求めるためのメッシュバス上での並列アルゴリズム
- 最大値問題に対するメッシュバス上でのO((log log n)^2)アルゴリズム
- PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)
- $\alpha$連結成分問題の計算複雑さの上昇について(計算量理論)
- 並列化が徐々に困難になるグラフ問題について
- 色塗り分け問題がP完全又はNCになる為の十分条件について(理論計算機科学とその周辺)
- 組合せ問題に対する RS 型ベクトルアルゴリズム
- RS型ベクトル機械の実際的応用の可能性について(計算および計算量理論とその周辺)
- 密な部分グラフ問題のNP完全性とそのSAT例題生成への応用
- AIMジェネレータによるバックトラック及び局所探索SATアルゴリズムの評価