我已经浏览了关于这个主题的所有链接，但仍然困惑为什么我们认为 NP Complete 是 NP。是不是只能在多项式时间内验证我们说NP完全问题是NP，但是我们有一些NP问题也可以在多项式时间内解决但是NP完全问题不能在多项式时间内解决那么那么这不是与将 NP 完全问题称为 NP 的性质相矛盾吗？
最佳答案
确定性图灵机可以在多项式时间内解决决策问题集 P。
然后是可以在多项式时间内由非确定性图灵机解决的决策问题集合 NP，即那些在给定一些见证字符串的情况下可以在多项式时间内验证其解决方案的问题。
确定性图灵机可以模拟非确定性图灵机，所以我们知道有一个指数时间算法可以解决NP问题。然而，我们不知道我们实际上是否没有 P = NP。
NP 完全问题是一个 NP 问题，至少与任何其他 NP 问题一样难。例如，SAT 是 NP 完全的，因为它可以有效地编码一个非确定性图灵机，解决 SAT 意味着模拟该机器。您可以通过证明先前已知的 NP 完全问题 B 可以在多项式时间内简化为 A 来证明问题决策问题 A 的 NP 完全性。这意味着如果 A 可以在多项式时间内求解，那么 B 也可以在多项式时间内求解，因此在某种意义上 A 至少和 B 一样难。
but we have some NP problems which can be solved in polynomial time as well
没错，因为 P 是 NP 的子集。
NP complete problems can't be solved in polynomial time
我们不确定。
doesn't this contradict the property of calling NP complete problems to be NP
完全没有。是的，我们知道 NP 中的问题也存在于 P 中。这并不意味着 NP 中没有不存在于 P 中的问题。但我们当然不知道后者。甚至可能是每个 NP 完全问题都在 P 中，在 P = NP 的情况下。
关于algorithm - 为什么说NP完全问题就是NP呢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31404296/