如果这些问题是NP完全问题，那么如何存在多项式时间算法来解决它们？

Question

如果这些问题是NP完全问题，那么如何存在多项式时间算法来解决它们？

3

我正在学习P、NP和NP-完全问题，遇到了一些问题。

如果可以在多项式时间内解决一个问题，那么它是P问题；如果可以在多项式时间内验证一个问题，那么它是NP问题。我也明白，如果一个问题既是NP问题，又可以从现有的NP-完全问题中规约得到，那么它就是NP-完全问题。

我知道SAT、3-SAT、Independent Set、Vertex Cover、Hamiltonian Cycle、Subset Sum和Traveling Salesman都是NP-完全问题。但是，我遇到了一个问题，被告知在一个图中确定是否存在5个顶点的独立集是多项式时间可解的，而不是NP-完全的。这让我感到困惑，因为我认为独立集问题是NP-完全问题。

那么，在哪些情况下这些“NP-完全”问题不是NP-完全问题，而是P问题呢？当给定一个问题时，如何确定它是P问题还是NP-完全问题？如果问题确实有多项式时间可解的解决方案，而我无法想出来，因此走了NP-完全的路线，那么我如何知道自己犯了错误？

- purpledots

一个由5个顶点组成的独立集合在多项式时间内似乎没有太多意义，因为如果所有参数都被限制，则可以在常数时间内解决此问题。P、NP等表示了渐近行为。此外，某些问题的子集可能更容易解决。例如，2-SAT可以在多项式时间内解决。因此，如果我们使用一个3-SAT问题，但每个子句只有两个不同的术语（如a或a或b），那么实际上这是2-SAT。 - Willem Van Onsem

@WillemVanOnsem 抱歉，我编辑了我的原始帖子。问题是决定一个图是否有一个独立的5个顶点集是P或NPC，而不是一个独立的5个顶点集是NPC。 - purpledots

最大独立集和旅行商问题是NP难问题，而不是NP完全问题。它们是组合优化问题，你无法在多项式时间内验证它们的解决方案。 - justinpc

1

https://en.wikipedia.org/wiki/Parameterized_complexity - David Eisenstat

如果问题确实有多项式可解的解决方案，而我无法想出来，因此选择了 NPC 路径，那也没什么好难过的，毕竟我们甚至不知道 P = NP = NPC 是否成立。 - Patrick87

3个回答

1

决定图中是否存在5个顶点的独立集实际上是可以在多项式时间内解决的。是的，决定/查找固定大小的独立集（或补集，查找固定大小的团）具有暴力算法，该算法通常是类似于n^k的多项式时间，其中k是固定大小 - 在您的情况下为n⁵。然而，NP完全问题的决策问题是对于任意大小的，其中k属于算法的输入。然后它变成指数时间。参数化复杂性领域进一步分析了这一点。

- Bergi

谢谢您的回复。我有些困惑，为什么当它是k时，它是NPC，但当数字替换k时，它就变成了P。如果k可以被任何数字替换，那么这不就意味着它可以针对替换k的任何数字进行求解吗？（不确定是否表达清楚） - purpledots

只要您将“k”替换为任何固定数字，它就是P。就像只要我们使用固定数字限制输入大小，任何算法都是O(1)一样。但是，一旦我们想要分析任意大的“k”的复杂性，我们就会得到NPC。 - Bergi

最大独立集问题不是NPC问题，而是NP难问题：https://en.wikipedia.org/wiki/Independent_set_(graph_theory)。我是否遗漏了什么？当k是任意值时，哪里是NP完全问题的决策问题？ - justinpc

@justinpc 在那篇文章中被称为“独立集决策问题”。 - Bergi

感谢和抱歉。 - justinpc

0

有一种类比可能会帮助你思考，尽管它并不是同样的东西。有一个数学证明，你不能在小于O(n*log(n))的时间内对任意长度的数组进行排序。然而，如果输入是“小”的或者你知道一些关于输入的信息，例如它仅包含k个字符，那么你可以使用其他方法更快地解决它，使用O(n)算法（例如，Redix sort）。

当我们试图概括这个问题时，因为我们没有任何关于输入的先前知识，事情变得更加困难（有时，NP-Complete 更难）。

- Tal Delbari

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- justinpc · Accepted Answer

寻找图的最大独立集问题是NP难问题，就像旅行商问题一样。它们都是优化问题，并且都涉及枚举一些情况，这些情况在输入大小上大于多项式。

给定一个数字k和一个n个顶点的图，寻找k个顶点的独立集是一个单独的问题，它有一个多项式时间的解决方案。这不是一个优化问题。

该解决方案受到以下事实的限制：五个顶点的子集最多只有C(n，k)个，对于每个子集，您需要检查最多C(k，2)条边。对于常数k，这些都是多项式时间的。