next up previous
: 近似アルゴリズム(Betterな解を求める) : 計算時間の比較(多項式=良い,指数関数=悪い) : 計算時間の比較(多項式=良い,指数関数=悪い)

最大クリーク問題, 最大充足割当問題に対する多項式時間アルゴリズムは作れるか

工夫を凝らさなければ, 両問題に対する簡単なアルゴリズムはすぐ作れる. 例えば,

最大クリーク問題では,


Step 1 頂点に1からnまでの番号をふる.
Step 2 1,2,…,nの全ての部分集合に対して以下を試す.
Step 2-1 その部分集合(に対応する部分グラフ)が 完全グラフかどうかチェックし, そうならば要素数を記憶.
Step 3 最大の要素数を出力する.

最大充足割当問題では,


Step 1 変数x1,x2,…,xnの真, 偽を代入してすべての 組合せをチェックする.
Step 2 一番多くの節が真になる組合せを出力する.

しかしこれらのアルゴリズムの実行時間を表す関数は, 両方ともnに関する指数関数になる. 今現在, 最大クリーク問題, 最大充足割当問題に対し, 多項式時間アルゴリズムは 発見されていない. さらに, それ以外の数多くの重要な問題(TSPやVLSIレイアウト問題)に対し, 指数時間のアルゴリズムは発見されているが, 多項式時間アルゴリズムは発見されていないという状況にある. そして多くの研究者が, そのような問題に対し多項式時間アルゴリズムは 存在しないであろうと予想している(P≠NP予想).


Koichi Yamazaki 平成12年3月15日