所有的NP问题都是NP完全的吗？

Question

NP-complete的定义是

如果是,问题是NP完全

1. 它属于NP类
2. NP中的所有其他问题多项式转换为它

因此,如果NP中的所有其他问题转化为NP完全问题,那么这是否也意味着所有NP问题也是NP完全的？如果它们是相同的,那么对两者进行分类有什么意义呢？

换句话说,如果我们有NP问题那么通过(2)这个问题可以转化为NP完全问题.因此,NP问题现在是NP完全的,NP = NP完全.这两个类都是等价的.

试图为自己澄清这一点.

Answer 1

所有的NP问题都是NP完全的吗？

只有当P = NP时.

Answer 2

不必要。NP 可能是一个已知的上限（即我们知道如何在非确定性多项式时间内求解它），但不是一个已知的下界（更有效的算法可能存在也可能不存在）。

这种问题的一个例子是图同构。

你的句子“如果我们有一个 NP 问题，那么 [...] 这个问题可以转化为一个 NP 完全问题”是不正确的，原因如下：P 中的任何问题也在 NP 中，但 P 中没有问题是 NP -完全（当然，除非P=NP）。