真的..我这周二将进行毕业考试的最后一次测试，这是我从未能理解的事情之一。我知道一个 NP 问题的解可以在多项式时间内验证。但是确定性与此有什么关系呢？
如果你能解释一下 NP 完全问题和 NP 难问题得名的由来，那就太好了（我相当确定我理解它们的含义，只是不明白它们的名称与其实际含义有什么关系）。
如果这很简单，那我很抱歉，我就是看不懂 (-:
感谢大家！
为什么NP问题被这样叫（以及NP-难和NP-完全）？
21
- Oren A
5个回答
20
P
一类可以由确定性图灵机在多项式时间内解决的问题。
NP
一类可以由非确定性图灵机在多项式时间内解决的问题（也可以由确定性图灵机在多项式时间内验证解答）。
NP-Hard
一类问题是“至少与NP中最难的问题一样难”。严格来说，一个问题在NP-Hard中当且仅当有一个NP完全问题可以在多项式时间内通过图灵可约归到它；（同样：如果可以通过具有该问题的oracle的oracle机器在多项式时间内解决）。这个名字的来源相当明显。
NPC
既属于NP又属于NP-Hard的问题集合。关于这个命名，“连维基百科”也不确定它为什么被命名为这样。
- Yuval Adam
1
这个问题与Pascal的回答一样--不在NP中的问题可能是NP难的。例如，任何在EXPTIME中的问题。 - Billy ONeal
12
我们从“非确定性”开始。一个确定性机器一次只能处于一个状态。我们可以制造它们。非确定性机器是一个理论构造，可以同时处于多个状态。（这里有类似于量子计算的相似之处，但对我们来说可能会误导，不予考虑。）
如果我们想用确定性机器解决一个问题，我们启动它，然后通过一系列步骤尝试找到一个问题的解。如果我们使用非确定性机器模型，它可以同时进行所有可能的步骤。
我们将涉及的问题集合称为决策问题：给定一个问题陈述，或者有解或者没有解。找到一个解或报告不存在。例如，假设您有一组逻辑语句：A或非B，B或C或D，非D或A或B，...。针对任意一个集合，您能够找到所有变量的真值，使得所有语句都为真吗？
现在，让我们考虑P 。假设我们通过n来表示问题的规模。规模可以是旅行商问题中的城市数量，在上面的问题中是逻辑语句的数量，等等。 针对特定的n，该问题需要特定的资源才能在给定系统上解决。 现在，如果我们加倍资源或计算能力，那么我们能够解决的问题规模会怎样变化？如果问题具有多项式复杂度，也就是说在P中，问题规模会增加一定比例。它可能加倍，或者增加40％，或10％。相反，如果它具有指数复杂度，问题规模会增加一定数量。我们通常认为P问题是可解的，指数问题是不可解的，因为随着问题规模的增大，这些问题变得非常困难，尽管这是一个简化。从非正式的角度来看，多项式复杂度是顺序地解决问题，而指数复杂度则必须查看所有可能的组合。
假设我们可以在确定性计算机上用多项式时间解决问题，则该问题属于P类问题。假设我们可以在非确定性计算机上用多项式时间解决它，这与能够在确定性计算机上多项式时间验证建议的解决方案是一回事。那么该问题属于NP类问题。关键在于，我们无法制造真正的非确定性计算机，因此一个问题属于NP类并不意味着解决它是实际可行的。现在让我们来看看NP完全问题。所有P类问题都属于NP类。对于NP类中的问题A和B，如果A属于P类，则B也属于P类。这可以通过找到将B重新表述为A类型问题的方法来实现。NP完全问题是指，如果它属于P类，则NP类中的每个问题都属于P类。你可能会猜到，找到一种将每个可能的问题重新陈述为特定问题的方式并不容易，我只会说逻辑语句问题（可满足性问题）是第一个被证明为NP完全问题的问题。之后就变得更容易了，因为只需要证明如果问题C属于P类，则可满足性问题也属于P类。
人们普遍认为有些问题属于NP类但不属于P类，并且最近发表了一篇证明（可能是有效的，也可能不是）。在这种情况下，NP完全程序是NP类中最难的问题。
有些问题不符合上述模式。旅行商问题通常表述为找到连接所有城市的最便宜的路线。这不是一个决策问题，我们无法直接验证任何建议的解决方案。我们可以将其重新陈述为一个决策问题：给定成本C，是否存在比C更便宜的路线？这个问题是NP完全问题，通过一点工作，我们可以像处理修改后的NP完全形式一样轻松地解决原始的TSP问题。因此，TSP问题是NP难问题，因为它至少与一个NP完全问题一样难。
- David Thornley
1
你指的是哪个最近发布的“证明”？ - Pacerier
10
NP问题被称为NP（非确定性多项式时间）是因为它可以通过非确定性图灵机在多项式时间内解决。
- sepp2k
1
4维基百科文章中提到，Billy ONeal援引的内容阐述了这与确定性图灵机对多项式时间可验证性的等价性。尽管这种表述更为直观，但并非导致NP名称产生的表述方式。 - grossvogel
7
让我们从NP开始：在NP中，N代表“nondeterministic（非确定性）”，P代表“polynomial time（多项式时间）”。如果您有一个可以在每个周期分支以并行探索可能性的非确定性图灵机，则可以在多项式时间内解决该类问题（“验证解决方案”替代定义最近变得流行，但它没有清楚地说明“N”的含义）。非确定性机器类似于具有无限处理器数量和能够在每个指令处fork()的并行计算机。
说一个问题Q是“NP-hard”意味着任何NP问题都可以通过多项式时间将其归约为问题Q。由于问题之间的“可以归约为”关系是一个顺序关系，因此您可以认为“NP-hard”意味着“至少与所有NP问题一样难”。
“NP-complete”问题只是NP中的NP-hard问题之一。我猜这类问题需要一个名称，但我不确定如何解释选择“complete”这个词。
说一个问题Q是“NP-hard”意味着任何NP问题都可以通过多项式时间将其归约为问题Q。由于问题之间的“可以归约为”关系是一个顺序关系，因此您可以认为“NP-hard”意味着“至少与所有NP问题一样难”。
“NP-complete”问题只是NP中的NP-hard问题之一。我猜这类问题需要一个名称，但我不确定如何解释选择“complete”这个词。
- Pascal Cuoq
8
@PascalCuoq，你能否提供一些关于NP定义的来源？你说“验证解决方案替代定义最近变得流行”，但从我查找到的来源来看，这似乎实际上是最初的定义。 - Pacerier
@Pacerier，你找到了哪些来源似乎暗示它是最初的定义呢？如果可以避免的话，我宁愿不花时间挖掘互联网之前发表的上世纪文章。我相信“NP”这个名称是以“非确定性定义”为参考选择的。如果它被定义为在多项式时间内可验证的问题类，为什么不将该类命名为“VP”呢？ - Pascal Cuoq
@PascalCuoq，我没有权威的来源证明“alt”定义的正确性。但是，正如你所说，“alt”是“流行的”定义，而且似乎是现状，因此如果你要声称另一种定义是原始定义，就有必要进行引证... - Pacerier
@Pacerier [1] Marianne Delorme，个人通信。说真的，我没有时间，就像我说的那样，如果你不喜欢我的答案，请给我一个反对票。一定要给任何不能适当解释为什么它被称为N P的答案投反对票，因为它是根据多项式验证时间定义的。或者写下你自己的答案，解释这两件事。我不必参与其中。 - Pascal Cuoq
@PascalCuoq，没错，我在想你可能能够脱口而出你听过那个定义的地方。你是第一个我看到提到“验证解决方案”不是（原始）定义的人。 - Pacerier
显示剩余3条评论
6
但是确定性与此有什么关系呢？
来自维基百科：
NP是所有决策问题的集合，其中“是”答案具有有效的证明，证明这个答案确实是“是”。更准确地说，这些证明必须可以在多项式时间内由确定性图灵机验证。
不过我不确定这些名称的历史。编辑：我有猜测，但我认为这并不无理。
NP-Hard是任何至少与NP中最难的问题一样困难的问题。因此，可以说所讨论的问题具有NP难度，因此为NP-Hard。
如果NP-complete中的任何一个问题可以快速解决，则NP中的每个问题也可以快速解决。因此，可以解决完整的NP问题集。
编辑2：维基百科的完全（复杂性）文章指出：
如果一个计算问题在形式上是复杂类中“最难”的或者“最具表现力”的问题之一，那么它就是该复杂类的完全问题。
来自维基百科：
NP是所有决策问题的集合，其中“是”答案具有有效的证明，证明这个答案确实是“是”。更准确地说，这些证明必须可以在多项式时间内由确定性图灵机验证。
不过我不确定这些名称的历史。编辑：我有猜测，但我认为这并不无理。
NP-Hard是任何至少与NP中最难的问题一样困难的问题。因此，可以说所讨论的问题具有NP难度，因此为NP-Hard。
如果NP-complete中的任何一个问题可以快速解决，则NP中的每个问题也可以快速解决。因此，可以解决完整的NP问题集。
编辑2：维基百科的完全（复杂性）文章指出：
如果一个计算问题在形式上是复杂类中“最难”的或者“最具表现力”的问题之一，那么它就是该复杂类的完全问题。
- Billy ONeal
1
1++ 为“完整”解释 - Oren A
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接