0

我认为，当证明一个问题 P 是 NP-Complete 时，我们应该将一个已知的 NPC 问题简化为 P。但是，看看独立集问题的解决方案，它似乎不是这样。

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

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

我在这里想念什么？这难道不是错的，因为它是反过来做的吗？

4

2 回答 2

2

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

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

如果我们知道 CLIQUE 在 NPC 中，那么我们可以很容易地证明 IS 在 NPC 中。

  1. 我们可以在 polytime 中简单地验证 IS。迭代顶点，确保每个顶点都有一条不在候选解中的边。
  2. 我们现在需要将 CLIQUE 简化为 IS。给定一个图形G和一个整数n，对于 CLIQUE，我们要检查是否存在 size 的 CLIQUE n。让H成为 的倒数G。如果您找到一个H大小为 in 的 IS n，则您有一个大小n为 inG且顶点相同的 CLIQUE。我们已将 CLIQUE 简化为 IS。

如果您要将 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 回答