什么是 NP 完全问题？为什么在计算机科学中如此重要？
在计算机科学中，什么是NP完全问题？
505
- Claudiu
7
6您可能对这个问题的答案感兴趣：https://dev59.com/yXVD5IYBdhLWcg3wBm5h。 - Dan Dyer
1我决定写下自己的答案，因为我不喜欢已接受答案的呈现方式，并包含了一个指向P=NP问题的链接。 - grom
1这里有一篇非常好的离散数学arsdigita讲座，讲解了NP完全问题是什么。前50分钟主要讨论布尔代数，所以如果您只对P，NP，NP完全性，布尔可满足性问题和约简概念感兴趣，请跳到第53分钟的开头。 - davitenio
1我们永远不会知道，因为当n很大时，它永远不会完成 ;) - Pete Alvin
2我非常喜欢并强烈推荐查看这个视频解释：https://www.youtube.com/watch?v=YX40hbAHx3s - Maksym Ovsianikov
显示剩余2条评论
14个回答
488
什么是NP？
NP是所有决策问题（具有是或否答案的问题）的集合，其中“是”答案可以通过确定性图灵机在多项式时间内验证（O(nk)，其中n是问题规模，k是常数）。多项式时间有时被用作快速或迅速的定义。
什么是P？
P是所有决策问题的集合，可由确定性图灵机在多项式时间内解决。由于它们可以在多项式时间内解决，因此也可以在多项式时间内验证。因此，P是NP的子集。
什么是NP-Complete？
如果且仅当每个NP中的其他问题可以快速（即在多项式时间内）转换为问题x时，问题x属于NP，则在NP中的问题x也属于NP-Complete。
换句话说：
- x在NP中，且
- NP中的每个问题都可以归约为x
因此，NP完全问题之所以如此有趣，是因为如果任何一个NP完全问题能够快速解决，那么所有的NP问题都可以被快速解决。
另请参阅帖子 什么是“P=NP?”，为什么它是一个著名的问题?
NP难问题是什么？
NP难问题至少与NP中最难的问题一样困难。请注意，NP完全问题也是NP难问题。但是，并非所有NP难问题都属于NP（甚至不是决策问题），尽管具有前缀NP。即NP-hard中的NP并不意味着非确定性多项式时间。是的，这很令人困惑，但它的使用已经深入人心，不太可能改变。
- grom
8
4“NP-hard”中的“NP”并不意味着非多项式，“NP-complete”（或任何其他地方）中的“NP”也是如此。 - sepp2k
1感谢sepp2k的纠正。我本意是要说它并不意味着NP（即非确定性多项式时间）。 - grom
1我认为你的答案比这个帖子中的其他答案更简单易懂。但是对于我来说，这仍然是一个非常难以理解的问题...这就是为什么算法专家能够获得高额报酬的原因吧。 - SoftwareSavant
5关于 NP：我认为它应该是：这个问题可以由非确定性图灵机来解决。（使用非确定性而不是确定性） - hqt
2@hqt 我写的是正确的。注意“验证过”的词语。你也是正确的，NP问题可以通过非确定性图灵机在多项式时间内解决。 - grom
显示剩余3条评论
236
NP 代表着非确定性多项式时间。
这意味着使用非确定性图灵机（像常规图灵机一样，但包括一个非确定性的“选择”函数），可以在多项式时间内解决该问题。基本上，一个解必须能够在多项式时间内进行测试。如果是这种情况，并且已知的 NP 问题可以使用给定问题的修改输入来解决（NP 问题可以被约化为给定问题），那么该问题就是 NP 完全问题。
从 NP 完全问题中得到的主要信息是，它不能以任何已知的方式在多项式时间内解决。NP-难/NP-完全是一种展示某些类别的问题无法在现实时间内解决的方式。
编辑：正如其他人所指出的，NP-完全问题通常有近似解。在这种情况下，近似解通常会使用特殊符号给出一个近似界限，告诉我们近似程度有多接近。
- Sam Hoice
14
2"...一个NP问题可以被归约到给定的问题上..." - 归约的重要限制是它应该是确定性多项式的。 - Rafał Dowgird
2O()符号是一种通用的数学符号，它在各个领域都有应用：近似算法确实可以给出O()的精度——在arxiv.org上查找任何近似算法论文即可。 - Ying Xiao
1@Yuval：只是为了明确。您之前的内容是完全错误的（除非P=NP）。从您的评论中，我感到您认为两个版本都是正确的。如果不是，我道歉。 - Aryabhatta
1如果一个问题是NP问题，并且已知的NP问题可以使用给定问题和修改后的输入解决[...]，那么这个问题是NP完全问题的说法是不正确的。一个问题是NP完全问题，当且仅当它是NP问题并且所有其他NP问题都可以归约到它。或者，一个问题是NP完全问题，当且仅当它是NP问题并且另一个NP完全问题可以归约到它。 - Adam Zalcman
46这个答案远远不够完整且难以理解，我不明白为什么它会有这么多点赞。 - nbro
显示剩余9条评论
39
基本上，这个世界的问题可以分为：
1）无解问题 2）难题问题 3）NP问题 4）P问题
1）第一个是没有解决问题。 2）第二个需要指数时间（即O（2 ^ n）以上）。 3）第三个被称为NP。 4）第四个是简单问题。
P：指问题在多项式时间内得以解决。
NP：指虽然还未找到多项式时间解决方案，但我们并不确定没有多项式时间解决方案。一旦提供了解决方案，则该解决方案可以在多项式时间内验证。
NP完全问题（NPC）：指虽然可以在多项式时间内验证，但我们仍未找到多项式时间解决方案。NPC问题比NP问题更困难，因此如果我们能证明对NPC问题有P解决方案，则可以找到P解决方案的NP问题。
NP难问题：指虽然还未找到多项式时间解决方案，但确定其不能在多项式时间内验证。NP难问题超越了NPC问题的难度。
- Marcus Thornton
1
很高兴看到这个答案，分类部分对整个概念非常表达清晰。我认为可交互问题是NP问题。 - PeerNet
36
NP-Complete是一个非常具体的概念，如果不小心就会定义错误。首先，NP问题是一种是/否问题，满足以下条件之一：
1. 对于问题的每个实例，都存在多项式时间的证明，证明答案为“是”，或者等价地，答案为“是”； 2. 存在一个多项式时间算法（可能使用随机变量），如果问题的答案是“是”，则该算法有非零概率回答“是”，如果答案是“否”，则它将100%回答“否”。换句话说，该算法必须具有小于100%的假阴性率和没有误报。
如果问题X是NP-Complete，则需满足以下条件：
1. X属于NP； 2. 对于NP中的任何问题Y，都存在从Y到X的“约化”，即一个将Y的任何实例转换为X实例的多项式时间算法，当且仅当Y实例的答案是“是”时，X实例的答案也是“是”。
如果X是NP-complete，并且存在一个确定性、多项式时间的算法可以正确地解决X的所有实例（0%误报，0%漏报），那么NP中的任何问题都可以通过约化到X来在确定性多项式时间内解决。
到目前为止，还没有人提出这样的确定性多项式时间算法，但也没有人证明不存在这样的算法（对于P = NP问题，有一百万美元的奖金可以领取）。这并不意味着你不能解决NP完全问题（或NP难问题）的特定实例。这只是意味着你不能有一种可靠地处理所有问题实例的东西，就像你可以可靠地对整数列表进行排序一样。你很可能能够想出一种算法，在所有实际的NP难问题实例上都能很好地工作。
1. 对于问题的每个实例，都存在多项式时间的证明，证明答案为“是”，或者等价地，答案为“是”； 2. 存在一个多项式时间算法（可能使用随机变量），如果问题的答案是“是”，则该算法有非零概率回答“是”，如果答案是“否”，则它将100%回答“否”。换句话说，该算法必须具有小于100%的假阴性率和没有误报。
如果问题X是NP-Complete，则需满足以下条件：
1. X属于NP； 2. 对于NP中的任何问题Y，都存在从Y到X的“约化”，即一个将Y的任何实例转换为X实例的多项式时间算法，当且仅当Y实例的答案是“是”时，X实例的答案也是“是”。
如果X是NP-complete，并且存在一个确定性、多项式时间的算法可以正确地解决X的所有实例（0%误报，0%漏报），那么NP中的任何问题都可以通过约化到X来在确定性多项式时间内解决。
到目前为止，还没有人提出这样的确定性多项式时间算法，但也没有人证明不存在这样的算法（对于P = NP问题，有一百万美元的奖金可以领取）。这并不意味着你不能解决NP完全问题（或NP难问题）的特定实例。这只是意味着你不能有一种可靠地处理所有问题实例的东西，就像你可以可靠地对整数列表进行排序一样。你很可能能够想出一种算法，在所有实际的NP难问题实例上都能很好地工作。
- David Nehme
4
1我不太喜欢自吹自擂，但我非常自豪于我的确定性多项式时间算法，我已经证明这种算法不存在。 ;) - Kyle Cronin
25我已经发现了一种非常奇妙的证明，这篇注释无法包含它;) - quick_dry
条件#2是P=?NP的陈述，而不是NP完备性的标准定义。它应该是：存在一个确定性多项式时间算法，可以将任何其他 NP实例X转换为此问题的实例Y，使得对于Y的答案是“是”当且仅当对于X的答案是“是”。 - Chris Conway
你必须小心，否则你会错误地定义它。正如这个答案所证明的那样。这个答案在某种程度上是正确的，但肯定不应该被接受。 - Windows programmer
35
NP-完全问题是一类问题。
类P包括那些可以在多项式时间内解决的问题。例如，它们可以在O(nk)的时间内解决，其中k是某个常数，n是输入的大小。简单来说，可以编写一个程序，在“合理”的时间内运行。
类NP包括那些可以在多项式时间内进行验证的问题。也就是说，如果我们得到了一个潜在的解决方案，那么我们可以在多项式时间内检查给定的解决方案是否正确。
一些例子是布尔可满足性（或SAT）问题，或者汉密尔顿回路问题。已知有许多问题属于类NP。
NP-完全意味着该问题至少与类NP中的任何问题一样困难。
这对计算机科学很重要，因为已经证明类NP中的任何问题都可以被转化为另一个NP-完全问题。这意味着解决任何一个NP-完全问题的解决方案也是所有NP问题的解决方案。
许多安全算法依赖于没有已知的解决方案的NP难问题。如果找到了解决方案，这肯定会对计算产生重大影响。
- Vincent Ramdhanie
4
这是错误的。NP问题可以转化为任何NP完全问题，而不是任何NP问题。这是一个很大的区别。 - David Nehme
此外，“这个问题和 NP 中的任何问题一样难”——没错，但更好的措辞应该是“至少和它一样难”。总的来说，这个答案比我看过的任何其他答案都更接近真相，也比不幸被接受的答案更接近真相。 - Windows programmer
感谢您的观察。我已经更新了答案，包括您的更正。 - Vincent Ramdhanie
1你对NP-Complete的定义不完整，你还需要指出NP-Complete问题也是NP（和NP-hard）问题，而不仅仅是与任何NP问题一样困难。如果你决定更改，我会给你点踩，如果你告诉我，我会取消点踩。 - nbro
23
这是一类问题，我们必须模拟每种可能性以确保我们有最优解。
对于一些 NP-完全问题，有很多好的启发式算法，但它们只能尽最大努力猜测最优解。
- Eric Wendelin
2
几乎正确。一个问题可能有一个非穷尽的解决方案，但仍然不是多项式性质的。 - Mark Bessey
1虽然不完全正确，但足够实用。不必要使用学究式的定义，尽管原帖作者可能想要这样的定义。这是一个很好的近似值！ - doug65536
21
如果您正在寻找 NP 完全问题的示例，那我建议您看一下 3-SAT。
基本思路是您有一个表达式在 合取范式 中，这意味着您有一系列通过 OR 连接的表达式，所有这些表达式都必须为真：
一种解决方案可能是 (a=T, b=T, c=F, d=F)。然而，尚未发现任何算法可在多项式时间内解决一般情况下的此问题。这意味着解决此问题的最佳方法基本上是采用暴力猜测和检查，并尝试不同的组合，直到找到有效的那一个。
3-SAT 问题的特殊之处在于，任何 NP 完全问题都可以转化为 3-SAT 问题。这意味着，如果您能找到一种多项式时间算法来解决此问题，那么您将获得 $1,000,000，更不用说得到世界各地计算机科学家和数学家的尊重和钦佩了。
基本思路是您有一个表达式在 合取范式 中，这意味着您有一系列通过 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，更不用说得到世界各地计算机科学家和数学家的尊重和钦佩了。
- nobody
2
也许是因为这里的其他解释让我感到困惑了，但是这句话不应该是“任何NP问题都可以在多项式时间内简化为3-SAT问题”吗？因为这不就是使3-SAT成为NP完全问题的原因吗？ - DubiousPusher
@DubiousPusher 不是的。答案已经正确阐述了。这张图片可以澄清 https://dev59.com/6lvUa4cB1Zd3GeqPqSDH#7367561 - jayeshsolanki93
14
说实话，维基百科可能是寻找这个问题答案最好的地方。
如果NP = P，那么我们能够比之前想象得更快地解决非常困难的问题。如果我们用P（多项式）时间解决一个NP-Complete问题，那么它可以应用于所有其他NP-Complete类别的问题。
- jjnguy
2
6如果NP=P，那么我们可以比之前预期的更快地解决非常困难的问题。——不对。如果NP=P，则存在解决方案（存在确定性算法来解决它们），但不能保证我们会知道它们是什么。 - Windows programmer
一个很公正的观点。 我猜任何证明 P = NP 的证明可能是建设性的（例如，发表一个三元可满足性问题的多项式算法）。 - Chris Conway
11
我们需要区分算法和问题。我们编写算法来解决问题，并且它们以某种方式扩展。虽然这是一种简化，但让我们将算法标记为“P”，如果其缩放足够好，则为“NP”。
了解我们要解决的问题而不是用于解决问题的算法是有帮助的。因此，我们将说所有具有良好缩放算法的问题都在“P”中。那些具有较差缩放算法的问题则在“NP”中。
这意味着许多简单问题也在“NP”中，因为我们可以编写不好的算法来解决简单问题。知道哪些NP中的问题真正棘手是很好的，但我们不想只说“这是我们还没有找到好算法的问题”。毕竟，我可能会想出一个问题（称之为X），我认为它需要一个超级惊人的算法。我告诉全世界，我能想出来解决X的最佳算法扩展不好，所以我认为X是一个非常困难的问题。但是明天，也许有比我更聪明的人发明了一个算法，可以解决X并且在“P”中。因此，这不是一个很好的定义难问题的方法。
同样，有许多人不知道NP中的问题没有找到好的算法。因此，如果我可以“证明”X是某种问题：一个良好的解决X的算法也可以用于以某种迂回的方式给出解决NP中“每个”其他问题的良好算法。那么人们可能会更加相信X是一个真正棘手的问题。在这种情况下，我们称X为NP-完全。
了解我们要解决的问题而不是用于解决问题的算法是有帮助的。因此，我们将说所有具有良好缩放算法的问题都在“P”中。那些具有较差缩放算法的问题则在“NP”中。
这意味着许多简单问题也在“NP”中，因为我们可以编写不好的算法来解决简单问题。知道哪些NP中的问题真正棘手是很好的，但我们不想只说“这是我们还没有找到好算法的问题”。毕竟，我可能会想出一个问题（称之为X），我认为它需要一个超级惊人的算法。我告诉全世界，我能想出来解决X的最佳算法扩展不好，所以我认为X是一个非常困难的问题。但是明天，也许有比我更聪明的人发明了一个算法，可以解决X并且在“P”中。因此，这不是一个很好的定义难问题的方法。
同样，有许多人不知道NP中的问题没有找到好的算法。因此，如果我可以“证明”X是某种问题：一个良好的解决X的算法也可以用于以某种迂回的方式给出解决NP中“每个”其他问题的良好算法。那么人们可能会更加相信X是一个真正棘手的问题。在这种情况下，我们称X为NP-完全。
- Tom
8
我听到过这样的解释："NP完备性"可能是算法研究中比较神秘的问题之一。"NP"代表"非确定多项式时间"，是一个复杂度类的名称，其中问题可以属于该类别。有关"NP"复杂度类的重要事情在于该类别内的问题可以通过多项式时间算法进行验证。
例如，考虑计数问题。假设桌子上有一堆苹果。问题是“有多少个苹果？”您将得到一个可能的答案8。通过使用算法（嗯，数苹果），您可以在多项式时间内验证此答案。数苹果需要O（n）（这是大写符号）时间，因为数每个苹果需要一步。对于n个苹果，您需要n步。这个问题属于NP复杂度类别。
如果可以证明问题既是NP-Hard又可以在多项式时间内进行验证，则将其分类为NP-complete问题。不必深入讨论NP-Hard，只需说有一些问题没有找到多项式时间解决方案。也就是说，要解决它们需要像n！（n的阶乘）这样的步骤。但是，如果您获得了NP-Complete问题的解决方案，可以在多项式时间内进行验证。
NP-Complete问题的一个经典例子是"旅行推销员问题"。
作者：ApoxyButt 来自：http://www.everything2.com/title/NP-complete
如果可以证明问题既是NP-Hard又可以在多项式时间内进行验证，则将其分类为NP-complete问题。不必深入讨论NP-Hard，只需说有一些问题没有找到多项式时间解决方案。也就是说，要解决它们需要像n！（n的阶乘）这样的步骤。但是，如果您获得了NP-Complete问题的解决方案，可以在多项式时间内进行验证。
NP-Complete问题的一个经典例子是"旅行推销员问题"。
作者：ApoxyButt 来自：http://www.everything2.com/title/NP-complete
- leizisdu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接