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

Question

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

我知道如果您可以在多项式时间内解决问题，那么问题就是 P，如果可以在多项式时间内验证，问题就是 NP。我也明白，如果问题是 NP 并且可以从现有的 NP-Complete 问题中减少，那么它就是 NP-Complete。

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

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

标签： algorithmnpnp-complete

Answer 1

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

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

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