什么是计算机科学的NP-complete？

Question

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

Answer 1

什么是NP？

NP是所有决策问题(带有是或否答案的问题)的集合,其中"是"答案可以在多项式时间内验证(O(n ^k),其中n是问题大小,k是a常数)由确定性图灵机.多项式时间有时用作快速或快速的定义.

什么是P？

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

什么是NP完全？

当且仅当 NP中的每个其他问题可以快速(即在多项式时间内)转换为x时,NP中的问题x也在NP完全中.

换一种说法:

1. x是NP,和
2. NP中的每个问题都可以简化为x

因此,NP-Complete如此有趣的原因在于,如果要快速解决任何一个NP-Complete问题,那么所有NP问题都可以快速解决.

另见帖子什么是"P = NP？",为什么这是一个如此着名的问题？

什么是NP-Hard？

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

Answer 2

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

这意味着可以使用非确定性图灵机(如常规图灵机,但也包括非确定性"选择"函数)在多项式时间内解决问题.基本上,解决方案必须在聚合时间内可测试.如果是这种情况,并且已知NP问题可以使用修改输入的给定问题来解决(NP问题可以减少到给定问题)那么问题是NP完成.

从NP完全问题中拿走的主要问题是它不能以任何已知方式在多项式时间内求解.NP-Hard/NP-Complete是一种表明某些类型的问题在实际时间内无法解决的方法.

编辑:正如其他人所说,NP-Complete问题通常有近似解决方案.在这种情况下,近似解通常使用特殊符号给出近似界限,告诉我们逼近的接近程度.

Answer 3

NP-Complete意味着非常具体的东西,你必须小心,否则你会得到错误的定义.首先,NP问题是一个是/否问题

1. 对于问题的每个实例都有多项式时间证明,答案为"是"或(等效)为"是"答案
2. 存在一个多项式时间算法(可能使用随机变量),如果对问题实例的答案为"是",则回答"是"的概率为非零,如果100%的话,则表示"否"为"否".答案是不." 换句话说,该算法必须具有小于100%的假阴性率并且没有误报.

问题X是NP-Complete,如果

1. X在NP中,并且
2. 对于NP中的任何问题Y,从Y到X都存在"减少":一种多项式时间算法,它将Y的任何实例转换为X的实例,使得Y实例的答案为"是",当且仅当如果答案X-instance为"是".

如果X是NP完全的并且存在确定性的多项式时间算法,其可以正确地解决X的所有实例(0%假阳性,0%假阴性),那么NP中的任何问题都可以在确定性多项式中求解 - 时间(减少到X).

到目前为止,还没有人提出这样一个确定性的多项式时间算法,但是没有人证明一个人不存在(对于任何能做任何一个问题的人来说都有一百万美元:这就是P = NP问题).这并不意味着您无法解决NP-Complete(或NP-Hard)问题的特定实例.它只是意味着你不能拥有能够在问题的所有实例上可靠地工作的东西,就像你可以对整数列表进行可靠的排序一样.您很可能能够提出一种算法,该算法在NP-Hard问题的所有实际情况下都能很好地工作.

Answer 4

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

         1)无法解决的问题2)难以处理的问题3)NP问题4)P-问题

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

P:指多项式时间问题的解.

NP:指多项式时间尚未找到解决方案.我们不确定没有多项式时间解决方案,但是一旦提供解决方案,就可以在多项式时间中验证此解决方案.

NP完全:在多项式时间中我们仍然没有找到解决方案,但可以在多项式时间中验证.NP中的NPC问题是比较困难的问题,所以如果我们能够证明我们有解决NPC问题的P,那么可以在P解决方案中找到NP问题.

NP Hard:指多项式时间尚未找到解决方案,但确定无法在多项式时间中进行验证.NP Hard问题超过NPC难度.

Answer 5

NP-Complete是一类问题.

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

该类NP包含在多项式时间内可验证的那些问题.也就是说,如果给出一个潜在的解决方案,那么我们可以检查给定的解在多项式时间内是否正确.

一些例子是布尔可满足性(或SAT)问题,或哈密顿循环问题.已知NP类中存在许多问题.

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

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

安全性中的许多算法取决于NP难问题不存在已知解决方案的事实.如果找到解决方案,它肯定会对计算产生重大影响.

Answer 6

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

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

Answer 7

如果您正在寻找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美元,更不用说全世界计算机科学家和数学家的尊重和钦佩.

Answer 8

老实说,维基百科可能是寻找答案的最佳地点.

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

Answer 9

我们需要分离算法和问题.我们编写算法来解决问题,并以某种方式扩展.虽然这是一个简化,但是如果缩放足够好,我们用"P"标记算法,如果不是,则标记"NP".

了解我们试图解决的问题,而不是我们用来解决它们的算法是有帮助的.所以我们会说所有具有良好缩放算法的问题都是"在P中".而具有不良缩放算法的那些是"在NP中".

这意味着许多简单的问题也是"在NP中",因为我们可以编写糟糕的算法来解决容易出问题的问题.很高兴知道NP中哪些问题真的很棘手,但我们不只是想说"这是我们没有找到一个好的算法".毕竟,我可以提出一个问题(称之为X)我认为需要一个超级惊人的算法.我告诉全世界我能用来解决X的最佳算法非常严重,所以我认为X是一个非常棘手的问题.但明天,也许比我更聪明的人发明了一种解决X并且在P中的算法.所以这不是一个很难定义的难题.

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

Answer 10

据我所理解

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

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

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

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

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

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

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

Answer 11

上面关于NP完全问题的定义是正确的，但是我认为我可能会对它们的哲学重要性加些抒情，因为还没有人解决这个问题。

几乎所有您遇到的复杂问题都是NP Complete。这个类有一个非常基础的东西，似乎在计算上与容易解决的问题有所不同。它们有点自己的风味，识别它们并不难。从根本上讲，这意味着您无法精确解决任何中等复杂的算法-调度，优化，打包，覆盖等。

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

请注意，两个非常著名的问题-图形同构和分解-都不是P或NP。

Answer 12

我听过一个解释，那就是：“ NP完全性可能是算法研究中比较神秘的想法之一。“ NP”代表“不确定的多项式时间”，并且是所谓的“复杂性类”的名称。NP复杂度类别的重要之处在于可以验证该类别中的问题通过多项式时间算法 例如，考虑计数的问题。假设桌子上有一束苹果。问题是“那里有多少个苹果？” 系统会为您提供一个可能的答案8。您可以通过使用对苹果计数的算法，在多项式时间内验证该答案。对苹果进行计数的时间为O（n）（表示为Big-oh），因为对每个苹果进行计数需要一步。对于n个苹果，您需要n个步骤。此问题属于NP复杂度类别。

如果可以证明问题是NP-Hard且可在多项式时间内验证的，则将其分类为NP-complete。在不深入讨论NP-Hard的情况下，可以说还存在一些尚未找到多项式时间解的问题。也就是说，它需要像n一样的东西！（n个阶乘）步骤来解决它们。但是，如果为您提供了NP完全问题的解决方案，则可以在多项式时间内对其进行验证。

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

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