有關獨立集問題的NP-完備性的問題

Question

我認爲，當證明問題P是NP-Complete時，我們應該將一個已知的NPC問題減少爲P.但是，查看獨立集問題，似乎不是這樣。

爲了證明獨立集是NP完全的，你可以得到圖G，找到它的逆G​​'，然後計算CLIQUE（G'）。但是，這是另一回事：它出現了一個問題P我不知道它是否是NPC，然後將它降低到知道的NPC問題。

Here是解決方案的一個例子。

我在這裏錯過了什麼？這是不是錯誤的，因爲它是這樣做的？

Answer 1

爲了證明P是NP完全問題，我們需要證明兩點：

1. 使得p存在於NP。
2. ，有一個polytime減少算法來減少一些NP完全問題Q可P.

如果我們知道CLIQUE是NPC，那麼，我們可以很容易地證明這是在全國人民代表大會。

1. 我們可以在polytime中平均地驗證IS。迭代頂點，確保每個頂點都不在候選解決方案中。
2. 我們現在需要將CLIQUE簡化爲IS。給定圖G和整數n，對於CLIQUE，我們要檢查是否存在大小爲n的CLIQUE。假設H是G的倒數。如果您發現大小爲n的H中的IS，則您的CLIQUE的大小爲n，其中G具有相同的頂點。我們將CLIQUE簡化爲IS。

如果你想減少IS到CLIQUE，你不會證明這是否在NPC中，除非你可以在NPC中減少一些其他問題到IS。

Answer 2

我覺得這個頁面可以幫助你http://mlnotes.com/2013/04/29/npc.html