关于独立集问题的NP完全性的问题 [英] Question about NP-Completeness of the Independent Set Problem

问题描述

我以为，当证明一个问题P是NP-Complete时，我们应该将一个已知的NPC问题简化为P.但是，在研究独立集问题的解决方案时，似乎并没有这样做.

I thought that, when proving that a problem P is NP-Complete, we were supposed to reduce a known NPC problem to P. But, looking at the solution to the Independent Set problem, it seems to not go this way.

要证明独立集是NP完全的，可取一个图形G，找到其逆G'，然后计算CLIQUE(G').但是，这是另一回事:遇到一个问题P，我不知道它是否是NPC，然后将其简化为已知的NPC问题.

To prove that Independent Set is NP-Complete, you take a graph G, find its inverse G', and then compute CLIQUE(G'). But, this is doing the other way around: it's taking a problem P I DON'T know if it's NPC and then reduces it to a know NPC problem.

这里是解决方案的示例.

我在这里想念什么?这不是错吗，因为它是相反的方式?

What am I missing here? Isn't this wrong, since it's doing it the other way around?

推荐答案

要证明P是NP完全的，我们需要显示两件事:

To prove that P is NP-complete, we need to show two things:

1. 那个P存在于NP中.
2. 有一种多时减少算法，可以将某些NP完全问题Q简化为P.

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

If we know that CLIQUE is in NPC, then we can easily prove that IS is in NPC.

1. 我们可以在多重时间内轻松地验证IS.迭代顶点，确保每个顶点在候选解决方案中都没有边缘.
2. 我们现在需要将CLIQUE降低为IS.给定一个图形G和一个整数n，对于CLIQUE，我们要检查是否存在大小为n的CLIQUE.设H为G的倒数.如果在大小为n的H中找到IS，则在G中具有大小为n的CLIQUE具有相同的顶点.我们已将CLIQUE简化为IS.

1. We can verify IS trivially in polytime. Iterate vertices, ensure that each has an edge not in the candidate solution.
2. We now need to reduce CLIQUE to IS. Given a graph G and an integer n, for CLIQUE we want to check if there's a CLIQUE of size n. Let H be the inverse of G. If you find an IS in H of size n, you have a CLIQUE of size n in G with the same vertices. We've reduced CLIQUE to IS.

如果要将IS简化为CLIQUE，除非您可以将NPC的其他一些问题简化为IS，否则您将无法证明两者都在NPC中.

If you were to reduce IS to CLIQUE, you wouldn't prove that either is in NPC unless you could reduce some other problem in NPC to IS.

这篇关于关于独立集问题的NP完全性的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！