为什么NP问题被称为（以及NP-HARD和NP COMPLETE）？

Question

真的..我在这个星期二的毕业最后测试，这是我永远无法理解的事情之一。我意识到，可以在多项式时间内对NP问题解决方案。但是，确定论与这有什么关系？
如果您可以向我解释NP-Complete和NP-Hard的名字，那就太好了（我很确定我得到了他们的含义，我只是看不到他们的名字对他们有什么用是）。
抱歉，如果这很琐碎，我似乎无法得到它（ - ：
谢谢！

Answer 1

p

所有问题的类别都可以通过 确定性 多项式时间的图灵机。

NP

所有问题的类别都可以通过 非确定性 多项式时间的图灵机（也可以通过 确定性 多项式时间的图灵机。）

np-hard

一类问题“至少与NP中最严重的问题一样困难”。正式地，在NP-HARD IFF中存在一个问题，有一个NP完整的问题是多项式时间Turing-tur-ter-tur-tir-tir-iff。 （另外：如果IFF可以在多项式时间内通过带有Oracle的oracle解决该问题）。这个名字的来源很明显。

NPC

既是NP又是NP-硬质的问题类别。关于命名， 甚至维基百科 不确定为什么会按原样命名。

Answer 2

让我们从“非确定性”开始。确定性机器一次可以处于一个状态。我们实际上可以做到。无确定的机器是一种理论构造，一次可以处于一个以上的状态。 （这里与量子计算有相似之处，但是出于我们的目的，它们具有误导性。无视它们。）

如果我们想解决确定性机器的问题，我们将开始使用，并通过一系列步骤来寻找问题。如果我们使用非确定的机器建模，则可以同时完成所有可能的一系列步骤。

我们将要关注的一组问题是决策问题：给定问题陈述，是否有解决方案。找到解决方案或报告没有。例如，假设您有一组逻辑语句：A或NOT-B，B或C或D，NOT-D或A或B，....给定任意集，您可以找到所有变量的真实值这样所有的陈述都是正确的？

现在，让我们考虑P。假设我们代表n的问题大小。大小可能是旅行推销员问题中的城市数量，上面问题中的逻辑语句的数量，无论如何。在一定的情况下，问题将需要一定数量的资源来解决给定系统。现在，如果我们将资源或计算能力加倍，我们可以解决的问题的大小会发生什么？如果问题是多项式复杂性，这意味着在P中，则大小会增加一定的分数。它可能会翻一番，或增加40％或10％。相反，如果它是指数级的复杂性，则大小会增加一定数量。我们通常认为P问题是可解决的，指数性问题是无法解决的，因为这些问题变得很大，尽管这是简化的。从非正式的角度来看，多项式复杂性能够顺序弄清问题，而指数则必须查看所有可能的组合。

假设我们可以在确定性机器上的多项式时间中解决问题。问题是在P中。假设我们可以在非确定机器上在多项式时间内解决它，这与能够在确定性机器上在多项式时间中验证所提出的解决方案相同。然后问题在NP中。这里的诀窍是我们不能制作真正的非确定机器，因此问题出现在NP中的事实并不意味着解决方案。

现在进入NP完整。 P中的所有问题均在NP中。对于NP中的问题A和B，我们也许可以说，如果A在P中，则B也是B。这是通过找到一种重述B作为一种问题来完成的。 NP完整的问题是，如果在P中，NP中的每个问题都在P中。只需说上述逻辑语句的问题（令人满意的问题）是第一个被证明是NP完整的。之后，这很容易，因为只需要证明问题C在P中，因此令人满意。

人们普遍认为，NP中存在一些问题，但不是P，并且最近发布了证明（这可能是也可能不会有效）。在这种情况下，NP完整程序是NP中最困难的问题。

有一些问题不适合这种模具。正常提出的旅行推销员问题是找到连接所有城市的最便宜的路线。这不是决策问题，我们无法直接验证任何建议的解决方案。我们可以将其重新确定为决策问题：给定成本C，是否有比C便宜的路线？这个问题是NP完整的，并且有了一些工作，我们可以轻松地解决原始TSP，就像修改后的NP完整形式一样。因此，TSP是NP-HARD，因为它至少与NP完整问题一样困难。

Answer 3

NP称为NP（非确定性多项式时间），因为NP问题可以通过非确定的图灵机在多项式时间内解决。

Answer 4

让我们从NP开始：在NP中，N用于“非确定性”，P用于“多项式时间”。如果您有一个不确定的图灵机器可以在每个周期内分支以并行探索可能性（“验证解决方案”的替代定义最近已经流行，但它并不清楚“ n”的含义）。可以将无确定的机器与具有无数处理器数量的平行计算机进行比较，并且能够 fork() 在每个说明中。

说问题q是“ np-hard”意味着NP中的任何问题都可以简化为问题Q（在多项式时间）。由于问题“可以简化为“问题之间”是一个订单关系，因此您可以将“ NP-HARD”视为“至少与所有NP问题一样困难”。

“ NP完整”问题只是NP中NP中的问题之一。我想问题类需要一个名称，但我不确定如何解释“完整”一词的选择。

Answer 5

但是，确定论与这有什么关系？

从 维基百科:

NP是所有决策问题的集合，“ Yes”招待会有效地证明了答案确实是“是”的事实。更准确地说，这些证明必须在多项式时间内通过 确定性 图灵机

不确定名称的历史。编辑：我有猜测。接下来是猜测，但我认为这是不合理的。

NP- hard是至少与NP中最困难的问题一样困难的任何问题。因此，可以说，所讨论的问题将具有NP硬度。因此，NP-HARD。

如果可以快速解决NP组中的任何一个问题，则NP中的每个问题也可以快速解决。因此，可以解决完整的NP问题集。

Edit2: 维基百科的完整（复杂性） 文章指出：

如果正式的意义上，复杂性类别是复杂性类别的计算问题，则是复杂性类中的“最难”或“最表现力”的问题之一