关于独立集问题的 NP 完备性问题

Question

我认为，当证明问题 P 是 NP 完全问题时，我们应该将已知的 NPC 问题简化为 P。但是，看看独立集问题的解决方案，似乎并没有走这条路。

为了证明独立集是 NP 完全的，您需要一个图 G，找到它的逆 G'，然后计算 CLIQUE(G')。但是，这是相反的做法：它正在处理一个我不知道它是否是 NPC 的问题，然后将其简化为一个已知的 NPC 问题。

这里是解决方案的一个示例。

我在这里缺少什么？这不是错误的吗，因为它是反过来的吗？

Answer 1

为了证明 P 是 NP 完全的，我们需要证明两件事：

1. P 存在于 NP 中。
2. 有一个多时间缩减算法可以将一些 NP 完全问题 Q 简化为 P。

如果我们知道CLIQUE在NPC中，那么我们就可以轻松证明IS在NPC中。

1. 我们可以在polytime中简单地验证IS。迭代顶点，确保每个顶点都有一条不在候选解中的边。
2. 我们现在需要将 CLIQUE 简化为 IS。给定一个图 G 和一个整数 n, ，对于 CLIQUE，我们要检查是否存在大小为 CLIQUE 的 CLIQUE n. 。让 H 是 G. 。如果您发现 IS H 尺寸的 n, ，你有一个规模大小的 CLIQUE n 在 G 具有相同的顶点。我们已将 CLIQUE 简化为 IS。

如果您要将 IS 简化为 CLIQUE，则无法证明其中任何一个都存在于 NPC 中，除非您可以将 NPC 中的其他问题简化为 IS。

Answer 2

我觉得这个页面可以帮助你 http://mlnotes.com/2013/04 /29/npc.html