有关独立集问题的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