独立集合問題の NP 完全性に関する質問

Question

問題 P が NP-Complete であることを証明するときは、既知の NPC 問題を P に還元する必要があると考えていました。しかし、独立集合問題の解決策を見ると、このようにはいかないようです。

独立集合が NP 完全であることを証明するには、グラフ G を取得し、その逆 G' を見つけて、CLIQUE(G') を計算します。しかし、これは逆のことをしています:それは問題を抱えています P それが NPC であるかどうかはわかりませんが、それを既知の NPC の問題に落とし込みます。

ここは解決策の一例です。

ここで何が足りないのでしょうか？逆のことをしているので、これは間違っていませんか？

Answer 1

P が NP 完全であることを証明するには、2 つのことを示す必要があります。

1. NP には P が存在します。
2. NP 完全問題の Q を P に削減するためのポリタイム削減アルゴリズムがあること。

CLIQUE が NPC にいることを知っていれば、IS が NPC にいることを簡単に証明できます。

1. ポリタイムでは IS を簡単に検証できます。頂点を繰り返し、それぞれの頂点に候補解に含まれないエッジがあることを確認します。
2. 次に、CLIQUE を IS に減らす必要があります。グラフを考えると G そして整数 n, 、CLIQUE の場合、次のサイズの CLIQUE があるかどうかを確認したい n. 。させて H の逆になる G. 。ISを見つけたら H サイズの n, のサイズの CLIQUE があります n で G 同じ頂点を持つ。CLIQUE を IS に縮小しました。

IS を CLIQUE に還元したとしても、NPC の他の問題を IS に還元できない限り、どちらかが NPC にあることを証明することはできません。

Answer 2

私は、このページはあなたを助けるかもしれないと思う http://mlnotes.com/2013/04 /29/npc.htmlする