所有 NP 问题都是 NP 完全问题吗？
NP完全问题的定义是，
如果一个问题
- 属于NP类，
- 则NP中的所有其他问题多项式变换为该问题
，则该问题是NP完全的。因此，如果NP中的所有其他问题都变换为NP完全问题，那么这不也是如此吗？是否意味着所有 NP 问题也是 NP 完全问题？如果两者相同，那么将它们分类有什么意义呢？
换句话说，如果我们有一个NP问题，那么通过（2）这个问题可以转化为一个NP完全问题。因此，NP 问题现在是 NP 完全问题，并且 NP = NP 完全问题。两个类都是等效的。
只是想为自己澄清这一点。
The definition of NP-complete is
A problem is NP-complete if
- it belongs to class NP
- all the other problems in NP polynomially transform to it
So, if all other problems in NP transform to an NP-complete problem, then does that not also mean that all NP problems are also NP-complete? What is the point of classifying the two if they are the same?
In other words, if we have an NP problem then through (2) this problem can transform into an NP-complete problem. Therefore, the NP problem is now NP-complete, and NP = NP-complete. Both classes are equivalent.
Just trying to clarify this up for myself.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
仅当 P = NP 时。
Only if P = NP.
未必。 NP 可能是一个已知的上限（即我们知道如何在非确定性多项式时间内求解它），但不是一个已知的下界（更有效的算法可能存在也可能不存在）。
此类问题的一个示例是图同构。
你的句子“如果我们有一个 NP 问题，那么 [...] 这个问题可以转化为一个 NP 完全问题”是不正确的，原因如下：P 中的任何问题也在 NP 中，但 P 中没有问题是 NP -完全（当然，除非P=NP）。
Not necessarily. It can happen that NP is a known upper-bound (ie. we know how to solve it in non-deterministic polynomial time) but not a known lower-bound (a more efficient algorithm may or may not exist).
An example of such a problem is graph isomorphism.
Your sentence "if we have an NP problem then [...] this problem can transform into an NP-complete problem" is incorrect for the simple following reason: any problem in P is also in NP, yet no problem in P is NP-complete (unless P=NP, of course).
如果问题
A多项式变换为问题B，这并不一定意味着问题B多项式变换为问题A。一个问题只能简化为一个同等或更大难度的问题。如果问题
C是NP问题，但不是NP完全问题，那么它可以多项式转化为任何NP完全问题，但这不足以使其成为NP完全问题，因为它不意味着 NP 多项式中的所有其他问题都会转换为问题C。If problem
Apolynomially transforms to problemB, that does not necessarily mean that problemBpolynomially transforms to problemA. A problem can only be reduced to a problem of equal or greater difficulty.If problem
Cis in NP, but is not NP-complete, then it can be polynomially transformed into any NP-complete problem, but that is not enough to make it NP-complete, because it does not imply that all the other problems in NP polynomially transform to problemC.至少应该可以证明一些NP完全问题也在P中。以从一组奇数中的复合奇数中筛选奇素数的问题为例。可以在 P 中导出执行此操作的方法。验证方法也可以在 P 中，如下面的链接所述。
https： //www.academia.edu/s/bcb7736e1e/proof-of-the-p-verses-np-problem-part-two?source=link
采取哥德巴赫猜想问题，可以证明为NP完全，线性时间内可以得到大于2的偶数相加的素数。每个哥德巴赫数都有自己的特征线，其中哥德巴赫点是具有质数坐标的点，这些点加起来就是哥德巴赫数。有关详细信息，请参阅下面的链接：
https://www.academia.edu/35904487/Proof_of_the_P_verses_NP_problem-第一部分
At least it should be possible to show that a number of NP complete problems are also in P. Take for example the problem of sieving odd prime numbers from from composite odd numbers in a set of odd numbers. It is possible to derive a method in P of doing it. The verification method can also be in P as is discussed in the link below.
https://www.academia.edu/s/bcb7736e1e/proof-of-the-p-verses-np-problem-part-two?source=link
Take the Goldbach conjecture problem, It can be shown to NP complete, the primes adding up to an even number greater than 2 can be obtained in linear time. Each Goldbach number has its own Characteristic line with Goldbach points as points with prime coordinates that add up to the Golbach number. See the link below for more information:
https://www.academia.edu/35904487/Proof_of_the_P_verses_NP_problem-part_one
我只是想指出另一个答案中显示 P=NP=NPC(if P=NP) 的数字是错误的。有两种情况：P 中的空语言 ϵ 及其补集 Σ* 永远不可能是 NPC。因为如果这两个在 NPC 中，我们就不能将 P/NP 中有实例的任何语言映射到 ϵ 并将 P/NP 中没有实例的任何语言映射到 Σ*，这与 NPC 的定义相矛盾：任何 NP 都可以简化为全国人大。
I just want to point out the figure showing P=NP=NPC(if P=NP) in the other answer is wrong. There are 2 cases: empty language ϵ and its complement ∑∗ in P can never be NPC. Because if these two are in NPC, we cannot map any language in P/NP with yes instance to ϵ and map any language in P/NP with no instance to ∑∗, which contradicts the definition of NPC: any NP can be reduced to NPC.