algorithm - 什么是计算机科学中的 NP 完全？

Question

什么是NP完全问题？为什么它在计算机科学中如此重要？

score 468 · Accepted Answer

什么是NP？

NP 是所有决策问题（带有是或否答案的问题）的集合，其中“是”答案可以在多项式时间 (O(n ^k ) 中得到验证，其中n是问题大小，k是常数）通过确定性图灵机。多项式时间有时被用作快速或快速的定义。

什么是P？

P 是可以在多项式时间内由确定性图灵机解决的所有决策问题的集合。由于它们可以在多项式时间内求解，因此它们也可以在多项式时间内得到验证。因此 P 是 NP 的子集。

什么是NP 完全？

当且仅当NP 中的所有其他问题都可以快速（即在多项式时间内）转换为 x 时，NP 中的问题 x 也属于 NP-Complete 。

换句话说：

x 在 NP 中，并且
NP 中的每个问题都可以归约为x

所以，NP-Complete之所以如此有趣，是因为如果要快速解决任何一个 NP-Complete 问题，那么所有NP问题都可以快速解决。

另见帖子什么是“P=NP？”，为什么它是一个如此著名的问题？

什么是NP-Hard？

NP-Hard 是至少与 NP 中最难的问题一样难的问题。请注意，NP-Complete 问题也是 NP-hard。NP然而，尽管有前缀，但并非所有 NP 难题都是 NP（甚至是决策问题）。也就是说 NP-hard 中的 NP 并不意味着非确定性多项式时间。是的，这很令人困惑，但它的使用是根深蒂固的，不太可能改变。

score 227 · Accepted Answer

NP代表非确定性多项式时间。

这意味着可以使用非确定性图灵机（类似于常规图灵机，但也包括非确定性“选择”功能）在多项式时间内解决问题。基本上，解决方案必须在多时间内可测试。如果是这种情况，并且已知的 NP 问题可以使用修改输入的给定问题来解决（NP 问题可以简化为给定问题），那么问题就是 NP 完全的。

一个 NP 完全问题的主要问题是它不能以任何已知的方式在多项式时间内解决。NP-Hard/NP-Complete 是一种表明某些类别的问题在现实时间内无法解决的方法。

编辑：正如其他人所指出的，NP-Complete 问题通常有近似解决方案。在这种情况下，近似解通常使用特殊符号给出近似界，该符号告诉我们近似值有多接近。

score 36 · Accepted Answer

NP-Complete 意味着非常具体的东西，你必须小心，否则你会弄错定义。首先，NP 问题是一个是/否问题，这样

对于问题的每个实例，都有多项式时间证明，答案是“是”，答案是“是”，或者（等效地）
存在一个多项式时间算法（可能使用随机变量），如果问题实例的答案是“是”，则该算法有非零概率回答“是”，并且在 100% 的情况下会说“否”，如果答案是不。” 换句话说，该算法必须具有小于 100% 的误报率并且没有误报。

问题 X 是 NP 完全的，如果

X 在 NP 中，并且
对于 NP 中的任何问题 Y，存在从 Y 到 X 的“归约”：一种多项式时间算法，它将 Y 的任何实例转换为 X 的实例，使得当且仅当 Y 实例的答案为“是”时如果答案 X-instance 是“是”。

如果 X 是 NP 完全的，并且存在可以正确解决 X 的所有实例的确定性多项式时间算法（0% 假阳性，0% 假阴性），则 NP 中的任何问题都可以在确定性多项式中解决时间（通过减少到 X）。

到目前为止，还没有人提出这样一种确定性多项式时间算法，但也没有人证明不存在这种算法（任何人都可以做到这一点，那就是一百万美元：这就是P = NP 问题）。这并不意味着您无法解决 NP-Complete（或 NP-Hard）问题的特定实例。这只是意味着您无法拥有可以可靠地处理问题的所有实例的东西，就像您可以可靠地对整数列表进行排序一样。您很可能会想出一个算法，该算法在 NP-Hard 问题的所有实际实例中都能很好地工作。

score 33 · Accepted Answer

基本上这个世界的问题可以归类为

1) 无法解决的问题 2) 棘手的问题 3) NP 问题 4) P 问题

1）第一个是没有解决问题的方法。2）第二个是需要指数时间（也就是上面的O(2^n)）。3）第三个称为NP。4）第四是容易的问题。

P：指多项式时间问题的一种解法。

NP：指多项式时间尚未找到解决方案。我们不确定是否存在多项式时间解决方案，但是一旦您提供了解决方案，该解决方案就可以在多项式时间中得到验证。

NP Complete：指在多项式时间内我们还没有找到解决方案，但可以在多项式时间内进行验证。NP 中的问题 NPC 是更难的问题，所以如果我们能证明我们对 NPC 问题有 P 解，那么可以在 P 解中找到 NP 问题。

NP Hard：指多项式时间还没有找到解决方案，但肯定无法在多项式时间中得到验证。NP Hard 问题超过 NPC 难度。

score 32 · Accepted Answer

NP-Complete 是一类问题。

该类P由可在多项式时间内解决的问题组成。例如，对于某个常数 k ，它们可以在 O(n ^{k ) 中求解，其中}n是输入的大小。简而言之，您可以编写一个在合理时间内运行的程序。

该类NP由在多项式时间内可验证的问题组成。也就是说，如果我们得到一个潜在的解决方案，那么我们可以检查给定的解决方案在多项式时间内是否正确。

一些例子是布尔可满足性（或SAT）问题，或哈密顿循环问题。已知有许多问题属于 NP 类。

NP-Complete意味着该问题至少与 NP 中的任何问题一样难。

它对计算机科学很重要，因为已经证明 NP 中的任何问题都可以转化为 NP-complete 中的另一个问题。这意味着任何一个 NP 完全问题的解决方案都是所有 NP 问题的解决方案。

许多安全算法依赖于这样一个事实，即 NP 难题不存在已知的解决方案。如果找到解决方案，肯定会对计算产生重大影响。

score 22 · Accepted Answer

这是一类问题，我们必须模拟每一种可能性，以确保我们有最佳解决方案。

对于一些 NP-Complete 问题，有很多很好的启发式方法，但它们充其量只是一个有根据的猜测。

score 19 · Accepted Answer

如果您正在寻找 NP 完全问题的示例，那么我建议您查看3-SAT。

基本前提是你有一个合取范式的表达式，这是一种说法，你有一系列由 OR 连接的表达式，它们都必须为真：

(a or b) and (b or !c) and (d or !e or f) ...

3-SAT 问题是找到一个解决方案，该解决方案将满足每个 OR 表达式恰好有 3 个要匹配的布尔值的表达式：

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

这个问题的解决方案可能是（a=T，b=T，c=F，d=F）。然而，在多项式时间的一般情况下，还没有发现可以解决这个问题的算法。这意味着解决此问题的最佳方法本质上是进行暴力猜测和检查，并尝试不同的组合，直到找到可行的组合。

3-SAT 问题的特别之处在于，任何 NP 完全问题都可以简化为 3-SAT 问题。这意味着，如果你能找到一个多项式时间算法来解决这个问题，那么你将获得1,000,000 美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

score 14 · Accepted Answer

老实说，维基百科可能是寻找答案的最佳场所。

如果 NP = P，那么我们可以比我们以前想象的更快地解决非常困难的问题。如果我们在 P（多项式）时间内只解决一个 NP-Complete 问题，那么它可以应用于 NP-Complete 类别中的所有其他问题。

score 11 · Accepted Answer

我们需要将算法和问题分开。我们编写算法来解决问题，它们以某种方式扩展。虽然这是一种简化，但如果缩放足够好，让我们用“P”标记算法，如果不是，则用“NP”标记。

了解我们试图解决的问题，而不是我们用来解决这些问题的算法，这很有帮助。所以我们会说所有具有良好缩放算法的问题都在“P”中。而那些具有较差缩放算法的算法是“在NP中”。

这意味着许多简单的问题也“在 NP 中”，因为我们可以编写糟糕的算法来解决简单的问题。知道 NP 中的哪些问题是真正棘手的问题会很好，但我们不只是想说“这是我们还没有找到好的算法的问题”。毕竟，我可以想出一个我认为需要超级惊人算法的问题（称之为 X）。我告诉全世界我能想出的最好的算法来解决 X 的扩展性很差，所以我认为 X 是一个非常棘手的问题。但是明天，也许比我更聪明的人发明了一种算法来解决 X 并且在 P 中。所以这不是对困难问题的一个很好的定义。

尽管如此，NP 中有很多问题没有人知道一个好的算法。因此，如果我可以证明X 是某种问题：也可以使用一种好的算法来解决 X，以某种迂回的方式，为NP中的所有其他问题提供一个好的算法。那么现在人们可能会更加确信 X 是一个真正棘手的问题。在这种情况下，我们称 X NP-Complete。

score 8 · Accepted Answer

我听过一个解释，那就是：“NP-Completeness 可能是算法研究中比较神秘的思想之一。”NP 代表“非确定性多项式时间”，是所谓的复杂性类的名称可以属于哪些问题。关于NP复杂性类的重要一点是，可以验证该类中的问题通过多项式时间算法。例如，考虑计算东西的问题。假设桌子上有一堆苹果。问题是“有多少个苹果？” 你会得到一个可能的答案，8。你可以在多项式时间内验证这个答案，方法是使用计算苹果的算法。计算苹果的时间为 O(n)（即 Big-oh 表示法），因为计算每个苹果需要一步。对于 n 个苹果，您需要 n 个步骤。这个问题属于 NP 复杂度类。

如果一个问题可以被证明是NP-Hard且在多项式时间内可验证，则该问题被归类为NP-complete 。无需深入讨论 NP-Hard，只需说某些问题尚未找到多项式时间解决方案即可。也就是说，它需要像 n! (n 阶乘) 步骤来解决它们。但是，如果您获得了 NP-Complete 问题的解决方案，您可以在多项式时间内对其进行验证。

NP 完全问题的一个典型例子是旅行商问题。”

作者：ApoxyButt 来自：http ://www.everything2.com/title/NP-complete

score 6 · Accepted Answer

上面对 NP 完全问题的定义是正确的，但我想我可能会对它们的哲学重要性大谈特谈，因为还没有人解决这个问题。

您遇到的几乎所有复杂问题都是 NP Complete。这个类有一些非常基本的东西，而且它似乎在计算上与容易解决的问题不同。它们有自己的味道，识别它们并不难。这基本上意味着您不可能准确解决任何中等复杂的算法——调度、优化、打包、覆盖等。

但是，如果您遇到的问题是 NP Complete，则并非所有问题都会丢失。人们在一个广阔且技术含量很高的领域研究近似算法，这将为您保证接近 NP 完全问题的解决方案。其中一些是非常强大的保证——例如，对于 3sat，您可以通过一个非常明显的算法获得 7/8 保证。更好的是，实际上，有一些非常强大的启发式算法，它们擅长为这些问题提供很好的答案（但不能保证！）。

请注意，两个非常著名的问题——图同构和因式分解——不知道是 P 还是 NP。

score 4 · Accepted Answer

据我所理解

P 是可以用确定性 TM 在多项式时间内解决的问题集。

NP 是一组需要在多项式时间内解决非确定性 TM 的问题。这意味着我们可以并行检查所有不同的变量组合，每个实例都需要多项式时间。如果问题是可解决的，那么至少有一个并行的 TM 实例会以“是”停止。这也意味着，如果您可以对变量/解决方案做出正确的猜测，那么您只需要检查它在多项式时间内的有效性。

NP-Hard 是问题比 NP 更难的集合。这意味着 NP-Hard 问题比 NP 集中的任何问题都更难。即使使用图灵机的非确定性，这些问题也是指数级的。因此，并行计算在解决这些问题时无济于事。

NP-Complete 是 NP 和 NP-Hard 的交集。据我了解，

NP-Complete 中的问题至少与 NP 集中最难的问题一样难。
所有 NP-Complete 问题的类别是等价的，即 NP-Complete 集中的一个问题可以简化为任何其他 NP-Complete 问题。这意味着如果任何 NP-Complete 问题都有一个有效的解决方案，那么所有 NP-Complete 问题都可以用相同的解决方案来解决。

如果 NP-Complete 集中的任何问题在多项式时间内是确定性可解的，那么整个 NP-Complete 集在多项式时间内是确定性可解的。此外，由于 NP-Complete 问题至少与 NP-Complete 中最难的问题一样难，因此 NP-Complete 中的所有问题（与 NP-Complete 中的问题相同或更容易）都将受到确定性多项式运行时间的限制，将 P 集扩展到 NP 集上，得到 P=NP。

如果我犯了任何错误，请告诉我。

score 3 · Accepted Answer

NP问题：-

NP问题是可以在非确定性多项式时间内解决的问题。
非确定性算法分两个阶段运行。
非确定性猜测阶段 && 非确定性验证阶段。

Np 问题的类型

NP完成
NP硬

NP完全问题：-

1 决策问题 A 如果具有以下两个属性，则称为 NP 完全：-

它属于NP类。
NP 中的所有其他问题都可以在多项式时间内转换为 P。

一些前：-

背包问题
子集和问题
顶点覆盖问题

score 1 · Accepted Answer

NP完全问题是一组问题，任何其他NP问题都可以在多项式时间内归约，并且其解决方案仍可以在多项式时间内得到验证。也就是说，任何 NP 问题都可以转化为任何 NP 完全问题。– 非正式地，NP 完全问题是至少与 NP 中的任何其他问题一样“难”的 NP 问题。