頂点カバー問題がNP完全であるということ その２

疲れていますか？私は疲れています。いわばご乱心です。なにがと聞かれても困りますが。そういうわけで今回は、寒さ厳しい折ということもあってよけいに寒くなるようなそういう無駄な部分を省こうと思います。ここまで、いろいろ意味を問われても困ります。

　

前回、頂点カバー問題（以下VCと略す）がクラスＮＰであると言うことをお話ししました。VCがＮＰ完全であると言うためには、ＮＰ完全であるという問題、今回はそれが3SATとなりますが、それと同等な問題である（SAT∝VCと表記する）ということを証明すれば良い訳です。

　

大まかな方法論としては、3SATの問題（「３SAT　その１」などを参照下さい）をVCの問題に翻訳します。

　

3SATはすべてのリテラル（ここではブール変数と同じと考えても可）の集合U={u1,u2,…,un}と、各節の要素の数が3つのブール変数に固定された節の集合C={c1,c2,…,cm}で一般的に表されます。

一方、VCについては、ノードの集合をV、枝の集合をEとしたとき一般的なグラフGをG={V,E}と表しすことにし、これがVCとして成立するノードの数をK（K≦｜V｜）と定義することにします。

3SATの問題をVCに翻訳するためにもう一つ、グラフＧをいろいろな部分集合の和であると定義しておきます。

　

このような準備をしてから、実際の翻訳作業に入ります。

　

　

　

　手順1.　3SATのリテラルui∈Uを部分グラフで表すことを考える

　　　　　そのような部分グラフをTi={Vi,Ei}と表すとき、Vi={ui,￢ui},Ei={{ui,￢ui}}とする

　

　　　　　このようにした場合、G={V,E}の頂点カバーであるようなノードの集合V'には
　　　　　uiか￢uiのどちらかが必ず含まれることになる　　　

　

　手順2．次に3SATの節cj∈Cについて同様のことを考え、そのような部分グラフを
　　　　 Sj={V'j,E'j}と表すこととすると、V'jとE'j次のように考えられる
　　　　　　
　　　　　　V'j={　a1[j],　a2[j],　a3[j]　},
　　　　　　E'j={　{a1[j], a2[j]},　 {a2[j], a3[j]}, 　{a3[j], a1[j]}　}

　

　　　　　ここで、a1[j], a2[j], a3[j]は新しく導入されたノードの表記ではあるが、
　　　　　当然ながら、a1[j]∈Vかつa２[j]∈Vかつa３[j]∈Vである

　　

　　　　　また、手順1で表したリテラルのときと同様に、このような場合
　　　　　G={V,E}の頂点カバーであるようなノードの集合V'には、
　　　　　a1[j], a2[j], a3[j]の三つのノードのうち少なくても二つのノードが
　　　　　含まれなければならない

　

　手順3．　G={V,E}においてノードの集合Vは以上で定義されたものですべて表される
　　　　　すなわち、

　　　　　　　

　　　　　　　　　　（※2014年5月7日　V'jの和集合の添え字がmでは無くnになっていました。
　　　　　　　　　　　　                      1≦j≦m　ですので、正しくはmです。お詫びして訂正いたします）

　手順4．　最後にG={V,E}において枝の集合Eについて考えると
　　　　　　すべてのcj∈Ｃについて、cj={xj,yj,zj}と節を表すとき
　　　　　　枝の部分集合を
　　　　　　　
　　　　　　　E"j={　{a1[j], xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
　　　　　と表すことにする

　　　　　こうしたときグラフＧの枝の集合Eを次のように定義する

　

　　　　　

　　　　　　　　（※2014年5月7日　上の図表の式と同じくE'jおよびE''jの和集合の添え字が
                                          mでは無くnになっていました。お詫びして訂正いたします）

また、ここでK=n+2mと定義する

　

　

以上のように翻訳することは明らかに多項式時間以内に可能だということがわかると思います。

　

今回は定義ばかりとなってしまいましたが、このような翻訳作業ということは、Cookの定理やSATを3SATに変換するというところでやったことにも似ています。

　

残りは、このようにして翻訳した結果がVCと同等だということを証明すればいいわけですが、それは次回ということで。

　

それにしてもうっぴょぴょん（乱心）

（※2014年5月7日　手順１.～手順4.までの文字を太線に変更）

頂点カバー問題がNP完全であるということ その１

今回から数回に分けて、頂点カバー問題（以下VCと呼ぶ）がNP完全であることを示していきます。手順としては、３SATがVCへ変換できること、すなわち、数式で書けば　３SAT∝VC　であることを証明することで示します。なお、NP完全についての説明は、「NP完全とその数学的定義　その１、その２」に書いていますので、私のように忘れた方は、もう一度そちらを読み返して下さいね。（え？）
　
念のために要点だけを言っておくと、「NP完全とその数学的定義その２」の終わりに、
　
補題1.3
　L1∈NP, L2∈NP,言語L1はNP完全でさらにL1∝L2ならば言語L2もNP完全である
　
ということを示しています。したがって、SAT∝３SATということから３SATはNP完全であることがすでに証明されていますので、今回も、３SAT∝VC　を証明すれば、VCはNP完全な問題であるということが証明されるわけです。
　
さらに、SAT、３SATがなんであったかさっとさんさっと復習しましょうか。詳しくは、（「充足問題　その１～その３」、「３SAT　その１～その３」の回などを参考にして下さいね）
　
まずSATですが、Uをブール変数（FかTの2値の値しか取らない変数）の集合とし、Cをブール変数の節（例えば{u1,¬u2}や{u1,u2,u4}）の集合(同じく{{u1,￢u2},{u1,u2,u4}}）とします。その時、この節集合CをTとするような、変数の集合Uの各変数の値に矛盾がないか（すなわち、真理関数がTになるか）ということでした。
　
３SATはSATのブール変数の節集合Cの各節のブール変数の数を3に統一するように変形したものでした。覚えてますかね？実は私はよく忘れます（え？）。
　
あっ、えっと、そういう話は置いておいて、さっとさっと説明説明っと。
　
まず、VCがNP困難な問題であることを簡単に述べましょう。あるグラフG(V,E)がありK≦|V|とします。このときK個のノードがVCであるかどうかは、実際に|V|個のノードから選ばれたK個のノードの組を総当たりで調べなければ分かりません。これは多項式時間では調べ尽くせないと言うことは容易に分かります。|V|個のノードから、K個のノードを選んでそれがVCであることを一つ一つ調べていくわけですから、組合わせの数は、オーダー（オーダーについては「クラスPとチューリングマシン その2」を参照して下さい）で|V|のK乗すなわち、最大のオーダーでなら|V|の|V/2|乗になるからです。ちなみに|V/2|の時に最大となるのは、VCとして調べているノードが半分を超えれば、残りのノードの数が少ない方から、VCとして調べているノードへの枝があるかどうかを調べるのと同等だからです。
　
ところが、一旦あるノードの組がVCであるということが分かれば、その場合にVCであることを調べるには多項式時間（クラスP）で済むことは、それらのノードの枝につながっているノードを調べて確認するだけ、ということから容易に分かります。したがって、VCはクラスNPの問題であるということが分かりました。
　
では、３SAT∝VC　であることの証明ですが、それは次回からということで