頂点カバー問題が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　であることの証明ですが、それは次回からということで