我正在研究P，NP和NP-Complete问题，我遇到了一些问题。
我知道如果你可以在多项式时间内解决问题就是P，如果在多项式时间内可以验证问题就是NP。我也明白，如果它是NP，则问题是NP-Complete，并且可以从现有的NP-Complete问题中减少。
我知道SAT，3-SAT，独立集，顶点覆盖，哈密顿循环，子集和和旅行推销员都是NPC。但我遇到了一个问题，我被告知决定图中是否存在一组独立的5个顶点实际上是多项式时间可解决而不是NPC。这让我感到困惑，因为我认为独立的问题是NPC。
那么它让我想知道，在什么情况下这些“NPC”问题不是NPC，实际上是P？遇到问题时，如何确定问题是P还是NPC？如果问题确实有一个多时间可解决的解决方案，我只是无法想出它，因此沿着NPC路径走了怎么办？我怎么知道我弄错了？
找到图的最大独立集的问题是NP难的，就像旅行商问题一样。它们都是优化问题，它们都涉及枚举大于输入大小的多项式的大量情况。
给定一个k数和n顶点图，找到一组独立的k顶点的问题是一个单独的问题，有一个多项式时间解决方案。这不是优化问题。
该解决方案受到以下事实的限制：最多有五个顶点的C(n, k)子集，并且对于每个子集，您需要检查最多C(k, 2)边缘。这些中的每一个都是n中的多项式，用于常数k。
决定图中是否存在一组独立的5个顶点实际上是多项式时间可解的
是的，决定/找到固定大小的独立集合（或互补，找到cliques of fixed size）有一个蛮力算法，它是多项式时间，通常类似nk，其中k是固定大小 - 在你的情况下是n5。
然而，NP完全的决策问题是任意大小，其中k属于算法的输入。然后它变成指数时间。 parameterised complexity领域进一步分析了这一点。
有一个类比可能会帮助你思考它，虽然它不是一回事。有一个数学证明，你不能在小于O（n * log（n））的范围内对任意长度数组进行排序。但是，如果输入是“小”或者您对输入有所了解，例如，它只包含k个字符，那么您可以使用其他方法使用O（n）算法更快地解决它（例如，Redix分类）。
当我们试图概括问题时，因为我们之前没有任何关于输入的知识，事情就更难了（有时候，NP-Complete更难）。