0

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

独立集合が NP 完全であることを証明するには、グラフ G を取り、その逆 G' を見つけ、CLIQUE(G') を計算します。しかし、これは逆のことをしています: それが NPC かどうか PI DON'T がわからない問題を取り上げ、それを既知の NPC 問題に減らします。

ソリューションの例を次に示します。

ここで何が欠けていますか？やり方が逆だからまずいんじゃないの？

4

2 に答える 2

2

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

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

CLIQUE が NPC 内にいることがわかっている場合、IS が NPC 内にあることは簡単に証明できます。

  1. IS を polytime で簡単に検証できます。頂点を反復し、それぞれに候補解にないエッジがあることを確認します。
  2. ここで、CLIQUE を IS に減らす必要があります。グラフGと整数が与えられたn場合、CLIQUE に対して size の CLIQUE があるかどうかを確認しますn。を の逆HとするG。Hサイズの IS が見つかった場合、同じ頂点を持つサイズnの CLIQUE があります。CLIQUE を IS に縮小しました。nG

IS を CLIQUE に縮小したとしても、NPC の他の問題を IS に縮小できない限り、いずれかが NPC にあることを証明することはできません。

于 2010-01-24T21:23:49.050 に答える
1

このページが役立つと思いますhttp://mlnotes.com/2013/04/29/npc.html

于 2013-04-29T17:33:07.433 に答える