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

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

306983 次浏览
小开

老实说，维基百科可能是寻找答案的最好地方。

如果NP = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于np -完全范畴内的所有其他问题。

小开

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

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

小开
最佳答案

NP代表< / em > < em >非确定性多项式时间。

这意味着使用非确定性图灵机(就像常规图灵机，但也包括非确定性“选择”函数)可以在多项式时间内解决问题。基本上，解必须在多边形时间内为可测试的。如果是这样的话，一个已知的NP问题可以用修改后的输入用给定的问题来解决(一个NP问题可以是减少到给定的问题)，那么这个问题是NP完全的。

从np完全问题中得到的主要东西是，它不能以任何已知的方式在多项式时间内解决。NP-Hard/NP-Complete是一种表明某些类型的问题在现实时间内无法解决的方法。

编辑:正如其他人所注意到的，np完全问题通常有近似解。在这种情况下，近似解通常给出一个近似界，用特殊的符号告诉我们这个近似有多接近。

小开

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

  1. 对于答案为"是"的问题的每个实例都有多项式时间证明，即答案为"是"，或者(等价地)
  2. 存在一种多项式时间算法(可能使用随机变量)，如果问题实例的答案是“是”，那么它有非零概率回答“是”，如果答案是“否”，则它会在100%的时间内回答“否”。换句话说，该算法的假阴性率必须小于100%，并且没有假阳性。

问题X是np完全的，如果

  1. X在NP中，并且
  2. 对于NP中的任何问题Y，都有一个从Y到X的“约简”:一个多项式时间算法，将Y的任何实例转换为X的实例，当且仅当X实例的答案是“是”时，Y实例的答案是“是”。

如果X是NP完全的，并且存在一个确定性的多项式时间算法，可以正确地解决X的所有实例(0%假阳性，0%假阴性)，那么NP中的任何问题都可以在确定性多项式时间中解决(通过归约到X)。

到目前为止，还没有人提出这样一个确定性多项式时间算法，但也没有人证明它不存在(任何一个可以做到这两种算法的人都有一百万美元:即P = NP问题)。这并不意味着您不能解决NP-Complete(或NP-Hard)问题的特定实例。它只是意味着你不能像对一组整数进行可靠排序一样，对一个问题的所有实例都可靠地工作。你很可能会想出一个算法，在NP-Hard问题的所有实际实例上都能很好地工作。

小开

np完全是一类问题。

类P由那些在多项式时间中可以解决的问题组成。例如，对于某个常数k，它们可以在O(nk)中求解，其中n是输入的大小。简单地说，你可以编写一个在合理的时间内运行的程序。

类NP由那些在多项式时间内可验证的的问题组成。也就是说，如果我们已知一个可能的解，那么我们可以在多项式时间内检验这个解是否正确。

一些例子是布尔可满足性(或坐)问题，或哈密顿周期问题。在NP类中有很多已知的问题。

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

它对计算机科学很重要，因为它已经证明了NP中的任何问题都可以改变了变成NP完全中的另一个问题。这意味着任何一个NP完全问题的解都是所有NP问题的解。

安全性中的许多算法依赖于NP困难问题没有已知解的事实。如果能找到解决方案，它肯定会对计算产生重大影响。

小开

如果你正在寻找一个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问题。这意味着如果你能找到一个多项式时间算法来解决这个问题，那么你就会得到1000000美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

小开

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

几乎你遇到的所有复杂问题都是NP完全的。这门课有一些非常基础的东西，从计算上看和容易解决的问题是不同的。它们有自己的味道，而且不难辨认。这基本上意味着任何适度复杂的算法都不可能精确地解决——调度、优化、包装、覆盖等。

但是，如果您遇到的问题是NP完全的，也不是所有的问题都失去了。有一个广阔的和非常技术化的领域，人们研究近似算法，这将给你保证接近NP完全问题的解决方案。其中一些是非常强大的保证——例如，对于3sat，你可以通过一个非常明显的算法得到7/8的保证。更好的是，在现实中，有一些非常强大的启发式，它们擅长为这些问题提供很好的答案(但不能保证!)。

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

小开

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

了解我们试图解决的问题，而不是我们用来解决它们的算法，是有帮助的。所以我们说，所有具有良好伸缩算法的问题都是"在P内"的。而那些有一个糟糕的缩放算法的是“NP”。

这意味着很多简单的问题也“属于NP”，因为我们可以编写糟糕的算法来解决简单的问题。知道NP中的哪些问题是真正棘手的问题是很好的，但我们不仅仅是想说“这是我们还没有找到一个好的算法的问题”。毕竟，我可以提出一个问题(称之为X)，我认为需要一个超级惊人的算法。我告诉全世界，我能想出的最好的算法来解决X的规模很糟糕，所以我认为X是一个非常棘手的问题。但是明天，也许比我聪明的人发明了一种算法来解决p中的X，所以这不是困难问题的一个很好的定义。

尽管如此，NP中仍有许多问题，没有人知道一个好的算法。因此，如果我可以证明, X是一个特定类型的问题:一个解决X的好算法可以也被使用，以某种迂回的方式，为NP中的其他问题每一个提供一个好算法。现在人们可能更相信X是一个棘手的问题。在这种情况下，我们称X为np完全。

小开

NP是什么?

NP是所有决策问题(答案是或否的问题)的集合，其中“yes”答案可以在多项式时间(O(nk)，其中n是问题大小，k是常量)由确定性图灵机组成。多项式时间有时被用作快或很快的定义。

P是什么?

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

非完全多项式是什么?

在NP中的问题x也在NP- complete 当且仅当中。在多项式时间内)转换成x。

换句话说:

  1. x在NP中，并且
  2. NP中的每个问题都是< em >可约< / em >到x

所以，让非完全多项式如此有趣的是，如果任何一个np完全问题可以快速解决，那么所有NP问题都可以快速解决。

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

赋权是什么?

NP- hard是指至少和NP中最难的问题一样难的问题。注意，np完全问题也是np难的。然而，并非所有NP难问题都是NP(甚至是决策问题)，尽管有NP作为前缀。也就是说NP-hard中的NP并不意味着非确定性多项式时间。是的，这令人困惑，但它的用法根深蒂固，不太可能改变。

小开

我听过一个解释，那就是:" np完备性可能是算法研究中比较神秘的概念之一。“NP”代表“非确定性多项式时间”，是所谓的复杂度类的名称，问题可以归属于此。关于NP复杂度类的重要事情是该类中的问题可以通过多项式时间算法验证。 以计算物品为例。假设桌子上有一堆苹果。问题是“有多少个苹果?”给你一个可能的答案，8。你可以在多项式时间内验证这个答案通过使用算法，嗯，数苹果。数苹果的时间是O(n)(这是Big-oh符号)因为数每个苹果只需要一步。对于n个苹果，需要n步。此问题属于NP复杂度类

如果一个问题能证明它在多项式时间内既是赋权又是可验证的，那么它就被归类为非完全多项式。在不深入讨论NP-Hard的情况下，只要说明某些问题的多项式时间解还没有找到就足够了。也就是说，它需要n!(n !)步来解它们。然而，如果给你一个np完全问题的解，你可以在多项式时间内验证它。

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

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

小开

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

1)无法解决的问题 2)棘手问题 3) np问题 4) P-Problem < / p >
第一个是没有解决问题的办法。 2)其次是需要指数时间(即O (2 ^ n)以上)。 3)第三个是NP。 4)第四个问题很简单

P:多项式时间问题的解。

NP:指多项式时间尚未找到一个解决方案。我们不确定有没有多项式时间的解决方案，但一旦你提供了一个解决方案，这个解决方案可以在多项式时间验证。

NP完全:是指在多项式时间中我们还没有找到一个解，但它可以在多项式时间中得到验证。NP中的NPC问题是比较困难的问题，所以如果我们能证明NPC问题有P个解，那么NP问题就能在P个解中找到。

NP困难:指多项式时间尚未找到解决方案，但它肯定无法在多项式时间内得到验证。NP难的问题超过NPC难的问题。

小开
np完全问题是一组问题，其中每一个问题都可以任意解决 其他np问题可以在多项式时间内约简，其解 仍然可以在多项式时间内验证。也就是说，任何NP问题都可以 转化为np完全问题。 非正式地说，NP完全问题是一个NP问题，至少是“难”

.

.
小开

NP问题:-

  1. NP问题是一类可以在非确定多项式时间内解决的问题。
  2. 非确定性算法分为两个阶段。
  3. 非确定性猜测阶段&&非确定性验证阶段。

Np问题的类型

  1. NP完全
  2. NP困难

NP完全问题:-

如果问题A具有以下两个性质，则称为NP完全问题

  1. 它属于NP类。
  2. NP中的任何其他问题都可以在多项式时间内转化为P。

一些例子:

  • 背包问题
  • 子集和问题
  • 顶点覆盖问题
小开

据我所知

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

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

NP- hard是指问题比NP更难的集合。这意味着NP- hard问题比NP集中的任何问题都要难。即使使用图灵机的非确定性，这些问题也是指数级的。所以并行计算在解决这些问题时没有帮助。

NP- complete是NP和NP- hard的交集集。根据我的理解，

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

如果np -完全集中的任何问题在多项式时间内确定可解，则整个np -完全集在多项式时间内确定可解。此外，由于NP-完全问题至少与NP集中最难的问题一样难，NP集中的所有问题(等于或容易于NP-完全集中的问题)将被确定性多项式的运行时间所限制，将P集扩展到NP集中，从而得到P=NP。

如果我弄错了，请告诉我。


提交答案