algorithm - 如果这些问题是 NP-Complete，那么如何解决它们的多项式时间算法？

Question

我正在研究 P、NP 和 NP 完全问题，并且遇到了一些问题。

我理解一个问题是P，如果你能在多项式时间内解决它，一个问题是如果它在多项式时间内可验证，则为NP。我也明白，如果问题是 NP 并且可以从现有的 NP 完全问题中减少，那么它就是 NP 完全问题。

我知道SAT、3-SAT、Independent Set、Vertex Cover、Hamiltonian Cycle、Subset Sum、Travelling Salesman都是NPC。但是我遇到了一个问题，有人告诉我，决定图中是否存在独立的 5 个顶点集实际上是多项式时间可求解的，而不是 NPC。这让我感到困惑，因为我认为独立集问题是 NPC。

那么这让我想知道，在什么情况下这些“NPC”问题不是 NPC 而实际上是 P？给定一个问题，如何判断是P问题还是NPC问题？如果问题确实有一个多时间可解决的解决方案怎么办，我只是无法想出它，因此走上了 NPC 的道路。我怎么知道我犯了错误？

Answer 1

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

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

解决方案受以下事实限制:最多有 C(n, k) 个五个顶点的子集，并且对于每个子集，您最多需要检查 C(k , 2) 边。这些中的每一个都是 n 中的常数 k 的多项式。