20

真的.. 我将在本周二进行最后一次毕业考试，这是我永远无法理解的事情之一。我意识到可以在多项式时间内验证 NP 问题的解决方案。但决定论与此有什么关系呢？
如果你能解释一下 NP-complete 和 NP-hard 的名字是从哪里得到的，那就太好了（我很确定我明白了它们的含义，我只是不明白它们的名字与它们的含义有什么关系是）。
对不起，如果那是微不足道的，我似乎无法理解（-：
谢谢大家！

4

5 回答 5

20

磷

可以在多项式时间内由确定性图灵机解决的所有问题的类别。

NP

可以在多项式时间内由非确定性图灵机解决的所有问题的类别（它们也可以在多项式时间内由确定性图灵机验证。）

NP-硬

一类“至少与 NP 中最难的问题一样难”的问题。形式上，一个问题在 NP-Hard 中，当且仅当存在一个 NP 完全问题，该问题是多项式时间图灵可约简到它；（另外：如果它可以在多项式时间内由带有预言机的预言机解决）。这个名字的来源很明显。

全国人大

既是 NP 又是 NP-Hard 的一类问题。关于命名，即使是维基百科也不确定为什么要这样命名。

于 2010-09-08T20:14:23.703 回答
12

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

如果我们想用确定性机器解决问题，我们启动它，它会通过一系列步骤来尝试找到问题。如果我们使用非确定性机器建模，它可以同时完成所有可能的一系列步骤。

我们要关注的一组问题是决策问题：给定一个问题陈述，要么有解决方案，要么没有解决方案。找到解决方案或报告没有解决方案。例如，假设你有一组逻辑语句：A or not-B, B or C or D, not-D or A or B, .... 给定一个任意集合，你能找到所有变量的真值吗？这样所有的陈述都是真实的？

现在，让我们考虑 P。假设我们用 n 表示问题的大小。大小可以是旅行商问题中的城市数量，上述问题中逻辑语句的数量，等等。给定某个 n，在给定系统上解决问题将需要一定数量的资源。现在，如果我们将资源或计算能力加倍，我们可以解决的问题规模会发生什么变化？如果问题是多项式复杂性，这意味着在 P 中，大小会增加一定比例。它可能会翻倍，或上涨 40% 或 10%。相反，如果它具有指数复杂性，则大小会增加一定数量。我们通常认为 P 问题是可解决的，而指数问题则随着问题变大而无法解决，尽管这是一种简化。从非正式的角度来看，

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

现在到 NP-complete。P中的所有问题都在NP中。对于 NP 中的问题 A 和 B，我们可以说如果 A 在 P 中，那么 B 也是。这是通过找到一种方法将 B 重述为 A 类问题来完成的。NP 完全问题是这样一个问题，如果它在 P 中，那么 NP 中的每个问题都在 P 中。正如您可能猜到的那样，找到一种方法将每个可能的问题重述为一个特定的问题并不容易，我会只是说上面的逻辑语句问题（可满足性问题）是第一个被证明的 NP 完全问题。之后就容易了，因为只需要证明如果问题 C 在 P 中，那么可满足性也是。

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

有些问题不适合这种模式。旅行商问题，正如通常所提出的，是找到连接所有城市的最便宜的路线。这不是决策问题，我们无法直接验证任何提议的解决方案。我们可以将其重述为一个决策问题：给定成本 C，有没有比 C 更便宜的路线？这个问题是 NP 完全的，只需一点点工作，我们就可以像修改后的 NP 完全形式一样简单地求解原始 TSP。因此，TSP 是 NP 难的，因为它至少与 NP 完全问题一样难。

于 2010-09-08T20:53:37.763 回答
10

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

于 2010-09-08T20:06:10.433 回答
7

让我们从 NP 开始：在 NP 中，N 代表“非确定性”，P 代表“多项式时间”。如果您有一个非确定性图灵机可以在每个周期分支以并行探索可能性，则可以在多项式时间内解决这类问题（“验证解决方案”替代定义最近很流行，但它并不清楚“N”是什么意思）。可以将非确定性机器比作具有无限数量处理器的并行计算机，并且能够处理fork()每条指令。

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

“NP-complete”问题只是 NP 中的一个 NP-hard 问题。我想这类问题需要一个名字，但我不知道如何解释“完整”这个词的选择。

于 2010-09-08T20:10:51.440 回答
6

但决定论与此有什么关系呢？

来自维基百科：

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

虽然不确定这些名字的历史。编辑：虽然我有猜测。以下是猜测，但我不认为这是不合理的。

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

如果 NP-complete 中的任何单个问题都可以快速解决，那么 NP 中的每个问题也可以快速解决。因此，可以解决完整的NP问题集。

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

如果计算问题在形式上是复杂性类别中“最难”或“最具表现力”的问题之一，则该计算问题对于复杂性类别来说是完整的

于 2010-09-08T20:07:00.870 回答