NP完全的定义是
一个问题是 NP 完全的，如果
- 它属于NP类
- NP多项式中的所有其他问题都转换为它
那么，如果 NP 中的所有其他问题都转换为 NP 完全问题，那么这是否也意味着所有 NP 问题也是 NP 完全问题？如果两者相同，那么对它们进行分类有什么意义？
换句话说，如果我们有一个 NP 问题，那么通过（2）这个问题可以转化为一个 NP 完全问题。因此，NP 问题现在是 NP-完全的，并且 NP = NP-完全。两个类是等价的。
只是想为自己澄清一下。
问问题
4160 次
5 回答
12
于 2011-09-09T21:20:05.670 回答
4
不必要。NP 可能是已知的上限（即我们知道如何在非确定性多项式时间内解决它）但不是已知的下限（可能存在也可能不存在更有效的算法）。
这种问题的一个例子是图同构。
你的句子“如果我们有一个 NP 问题，那么 [...] 这个问题可以转化为一个 NP 完全问题”是不正确的，原因很简单：P 中的任何问题也在 NP 中，但 P 中没有问题是 NP -完成（当然，除非 P=NP）。
于 2011-09-09T21:20:19.090 回答
0
如果问题A多项式转化为问题B，那并不一定意味着问题B多项式转化为问题A。一个问题只能归结为一个同等或更大难度的问题。
如果问题C在 NP 中，但不是 NP 完全问题，那么它可以多项式转化为任何 NP 完全问题，但这不足以使其成为 NP 完全问题，因为它并不意味着所有其他问题都在 NP 中多项式转换为问题C。
于 2017-06-17T09:06:21.857 回答
0
至少应该有可能证明许多 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-part_one
于 2018-02-14T14:49:18.420 回答
0
我只想指出另一个答案中显示 P=NP=NPC(if P=NP) 的图是错误的。有 2 种情况：空语言 ϵ 及其在 P 中的补集 ∑∗ 永远不可能是 NPC。因为如果这两个在 NPC 中，我们不能将 P/NP 中任何有实例的语言映射到 ϵ，而将 P/NP 中没有实例的任何语言映射到 ∑∗，这与 NPC 的定义相矛盾：任何 NP 都可以简化为全国人大。
于 2021-04-23T17:42:15.400 回答