著者

宮崎 修一 岩間 一雄

雑誌

全国大会講演論文集

巻号頁・発行日

vol.47, pp.79-80, 1993-09-27

---

NP完全問題は,問題のサイズに対して多項式時間で解くアルゴリズムが知られていない問題の代表例である.これらの問題は多項式程度の違いを無視すれば,同じ計算時間で解けるという点で,同じクラスに属する.即ち,ある問題を多項式時間で別の問題に変換することができる.これらの変換は,問題のNP完全性を証明するのに用いられてきた.多項式時間であればどのような変換であってもかまわないという大雑把なものであったが,問題を変換して解くという実用性を考えれば,変換の効率を良くすることが大切になってくる.例えば,CNF論理式の充足可能性問題(SAT)に対する効率の良いアルゴリズムに局所探索法と呼ばれるものがある.ハミルトン閉路問題をSATに変換し,局所探索法で解く場合には,変換によって得られる論理式のの変数の数によって計算時間に格段の差があることが分かっている.本研究では,別のNP完全問題である,グラフの頂点彩色可能性問題をSATに変換する方法を考察してみた.本稿では,まず,頂点数N,色数Kとして,N log K変数での比較的自然な変換の方法を述べる.次に,N logよりも少ない変数の数で変換する方法を2つ述べる.1つは,グラフ中に枝が少ないときに有効であり.もう1つは,枝の数が多いときに有効であることが分かった.NP完全問題は手に負えないという形で統一的に論じられることが多く,個々の問題の難しさの違いはあまり論じられていないようにみえる.本論文で述べている手法,つまりNP完全問題PをSATに変換するのに何変数必要であるかは,ある意味でPの難しさのメジャーになりうると考えられる.計算ステップ数,領滅量等の従来のメジャーとの大きな違いは,定数係数の違い,あるいは定数の差さえも十分に議論でき,それが重要とみなされる点である.