logo标签列表

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

computer-sciencecomplexity-theorynp-completenp
5
NP-complete的定义是：
如果一个问题满足以下两个条件，则它是NP-complete问题：
1. 属于NP类问题； 2. 所有其他NP问题都可以在多项式时间内归约到该问题。
因此，如果所有其他NP问题都可以转化为NP-complete问题，那么这是否意味着所有NP问题也都是NP-complete问题？如果它们是相同的，那么分类的意义何在？
换句话说，如果我们有一个NP问题，那么通过（2），这个问题可以转化为一个NP-complete问题。因此，NP问题现在也是NP-complete问题，而且NP = NP-complete。两个类是等价的。
希望这能为您澄清问题。
旧评论已被删除，因为它是不正确的 - 这里有一个有趣的NP（P $U$ NP-C）问题列表。http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc - seagaia
我觉得我之前说的评论是错误的。下面的理解是否正确？：NP \ (P U NP-C)中的问题可以简化为NP-C问题（所以如果一个 NP-C 问题可以有效地解决，那么我们可以将 NP-I 问题转化为 NP-C 问题，并高效地解决，然后将解决方案映射回来）。 - seagaia
5个回答
16
不错的可视化，但它并没有解释问题中定义上的矛盾或推理错误。 - user2623008
5
不一定。可能存在NP是已知上界（即我们知道如何在非确定性多项式时间内解决它），但不存在已知下界（可能存在更有效的算法，也可能不存在）的情况。
一个这样的问题的例子是图同构。
你的句子“如果我们有一个NP问题，那么[...]这个问题可以转化为一个NP完全问题”是错误的，原因很简单：P中的任何问题也都在NP中，但除非P=NP，否则没有任何P中的问题是NP完全的。
4
如果P属于NP问题集，并且所有的NP问题可以转化为NP完全问题，那么P也必须能够转化为NP完全问题。 - entitledX
2
如果问题 A 多项式地转化为问题 B，那并不意味着问题 B 一定可以多项式地转化为问题 A。一个问题只能被简化为相等或更难的问题。
如果问题 C 属于 NP，但不是 NP 完全问题，则它可以被多项式地转化为任何 NP 完全问题，但这还不足以使其成为 NP 完全问题，因为它并没有暗示着 NP 中的所有其他问题都可以多项式地转化为问题 C。
0

我只想指出其他答案中显示P=NP=NPC（如果P=NP）的图表是错误的。有两种情况：空语言ϵ和它的补集∑∗在P中永远不可能是NPC。因为如果这两个都在NPC中，我们就无法将任何具有yes实例的P / NP语言映射到ϵ，并将任何具有no实例的P / NP语言映射到∑∗，这与NPC的定义相矛盾：任何NP都可以被归约为NPC。

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接