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

StackOverflow https://stackoverflow.com/questions/210829

题

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

有帮助吗？

解决方案

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

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

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

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

其他提示

什么是 NP ？

NP是所有决策问题的集合（带有是或否答案的问题） ）多项式时间内的“是” - 答案可以 验证 （O（n k ）其中 n 确定性图灵机<问题大小， k 是常数） / A>。多项式时间有时用作 fast 或快速的定义。

什么是 P ？

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

什么是 NP-Complete ？

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

换句话说：

  1. x在NP中，
  2. NP中的每个问题都是 可缩小 到x

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

    另见什么是“P = NP？“，为什么这是一个如此着名的问题？

    什么是 NP-Hard ？

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

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

  1. 对于每个问题实例都有多项式时间证明，其中“是”是回答答案是“是”或（等效地）
  2. 存在多项式时间算法（可能使用随机变量），其具有非零回答“是”的概率。如果问题实例的答案是“是”，那么并会说“不”如果答案是“否”，则100％的时间。换句话说，算法必须具有小于100％的假阴性率且没有误报。

    3. 问题X是NP-Complete，如果

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

      3. 如果X是NP完全的并且存在确定性的多项式时间算法，它可以正确地解决X的所有实例（0％假阳性，0％假阴性），那么NP中的任何问题都可以在确定性中得到解决 - 多项式时间（减少到X）。

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

NP-Complete是一类问题。

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

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

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

NP-Complete 表示问题至少与NP中的任何问题一样难。

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

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

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

＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 1）无法解决的问题 ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 2）难以解决的问题 ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 3）NP问题 ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 4）P-问题

＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 1）第一个是解决问题的方法。 ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 2）第二个是需要指数时间（即上面的O（2 ^ n））。 ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 3）第三个称为NP。 ＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; 4）第四个是容易的问题。

P：指多项式时间问题的解决方案。

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

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

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

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

对于一些NP-Complete问题，有许多良好的启发式方法，但它们只是一种有根据的猜测。

如果您正在寻找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 ，更不用说世界各地的计算机科学家和数学家的尊重和钦佩。

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

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

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

了解我们试图解决的问题，而不是我们用来解决它们的算法是有帮助的。因此，我们将说具有良好缩放算法的所有问题都是“在P中”。并且具有差的缩放算法的那些是“在NP中”。

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

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

上述NP完全问题的定义是正确的，但我认为我可能对其哲学重要性抒情，因为还没有人解决这个问题。

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

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

请注意，两个非常着名的问题 - 图同构和因子 - 不知道是P还是NP。

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

如果在多项式时间内可以显示 NP-Hard 和可验证，则问题被归类为 NP-complete 。在没有深入讨论NP-Hard的情况下，可以说有些问题没有找到多项式时间解决方案。也就是说，它需要n！ （n阶乘）步骤来解决它们。但是，如果您获得了NP-Complete问题的解决方案，则可以在多项式时间内对其进行验证。

NP-Complete问题的典型例子是旅行商问题。“

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

NP 问题：-

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

Np 问题的类型

  1. NP完全
  2. NP硬质

NP 完全问题：-

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

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

一些前：-

  • 背包问题
  • 子集求和问题
  • 顶点覆盖问题
NP完全问题是一组问题，其中任何一个问题 其他NP问题可以在多项式时间内减少，并解决其问题 仍然可以在多项式时间内验证。也就是说，任何NP问题都可以 转化为任何NP完全问题。 ＆＃8211;非正式地，NP完全问题是NP问题，其至少是“坚韧”的问题。 与NP中的任何其他问题一样。

NP问题是可以在多项式时间内创建验证解决方案的计算机算法。

NP-Complete问题是NP，但如果你能在多项式时间内解决它（称为P），则所有NP问题都是P.

所以得到破解。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top