NP问题是否也完整? [英] Are all NP problems also NP-complete?
问题描述
NP完全的定义是
如果问题是NP完全问题
A problem is NP-complete if
- 它属于NP类
- NP中的所有其他问题都会通过多项式转化为它
因此，如果NP中的所有其他问题都转变为NP完全问题，那是否还不意味着所有NP问题也都是NP完全问题?如果两者相同，对它们进行分类有什么意义呢?
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?
换句话说，如果我们有一个NP问题，那么通过(2)，这个问题可以转化为一个NP完全问题.因此，NP问题现在是NP完全的，并且NP = NP完全的.这两个类是等效的.
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.
推荐答案
不一定. 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.
您的句子如果我们有一个NP问题，那么这个问题可以转化为一个NP完全问题"，原因很简单，原因很简单:P中的任何问题也在NP中，而在P中也没有问题P是NP完全的(当然，除非P = NP).
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).
这篇关于NP问题是否也完整?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
