P，NP，NP-Complete和NP-HARD的定义是什么？

https://cs.stackexchange.com/questions/9556

16-10-2019
|

题

我正在参加有关的课程计算和复杂, ，并且无法理解这些术语的含义。

我所知道的是，NP是NP完整的子集，这是NP-HARD的子集，但我不知道它们的实际含义。维基百科也不会有帮助，因为解释仍然太高了。

解决方案

我认为Wikipedia文章$ mathsf {p} $, $ mathsf {np} $, ，和 $ mathsf {p} $ VS. $ mathsf {np} $ 很好。我仍然会说：第一部分, 第二部分

我将在括号内使用备注来讨论一些技术细节，如果需要，您可以跳过。

第一部分

决策问题

有各种计算问题。但是，在计算复杂性理论课程的介绍中，更容易专注于 决策问题, ，即答案是是或否。还有其他类型的计算问题，但是在大多数情况下，有关它们的问题可能会简化为有关决策问题的类似问题。此外，决策问题非常简单。因此，在计算复杂性理论课程中，我们将注意力集中在决策问题的研究上。

我们可以通过回答是的输入子集确定决策问题。这简化了符号，允许我们写作$ x in q $ 代替 $ q（x）=是$ 和$ x Notin Q $ 代替 $ q（x）=否$.

另一个观点是我们正在谈论 会员查询 在一组。这是一个示例：

决策问题：

输入：自然数字 $ x $,
问题：是 $ x $ 偶数吗？

会员问题：

输入：自然数字 $ x $,
问题：是 $ x $ 在 $ even = {0,2,4,6， cdots } $?

我们将输入上的是的答案称为接受输入和对输入的无答案拒绝输入。

我们会看算法出于决策问题并讨论这些算法在其中的有效效率使用 可计算资源。我将依靠您的直觉，从诸如C之类的语言编程中，以代替正式定义算法和计算资源的含义。

备注：1。如果我们想正式而准确地完成所有操作，我们需要修复像标准一样的计算模型图灵机型号恰恰定义算法及其对计算资源的用法的含义。 2.如果我们想谈论模型无法直接处理的对象的计算，我们需要将它们编码为机器模型可以处理的对象，例如，如果我们使用的是图灵机，则需要编码自然数字和图形等对象作为二进制字符串。

$ mathsf {p} $ =有效算法的问题发现解决方案

假使，假设 有效的算法 最多最多使用的算法 多项式 计算资源的数量。我们关心的主要资源是最坏的情况 运行时间 关于输入大小的算法，即算法采用大小的基本步骤的数量 $ n $. 。输入的大小 $ x $ 是 $ n $ 如果需要 $ n $- 存储的计算机存储器 $ x $，在这种情况下我们写 $ | x | = n $。所以 通过有效的算法，我们的意思是具有多项式运行时间的算法.

这假设多项式时间算法捕获了有效算法的直观概念，称为科汉姆的论文. 。我目前不会讨论是否 $ mathsf {p} $ 是有效解决问题的正确模型，以及是否 $ mathsf {p} $ 在实践和相关问题中可以或不捕获可以有效计算的内容。就目前而言，有充分的理由做出这一假设，因此出于我们的目的，我们假设是这种情况。如果您不接受Cobham的论文，它不会使我在下面写的内容不正确，我们唯一会失去的是直觉关于实践中有效的计算。我认为这对于开始学习复杂性理论的人是一个有用的假设。

$ mathsf {p} $ 是可以有效解决的决策问题类别,
IE具有多项式时间算法的决策问题。

更正式的是，我们说一个决策问题 $ Q $ 在 $ mathsf {p} $ iff

有一个有效的算法 $ a $ 这样
对于所有输入 $ x $,

如果 $ q（x）=是$ 然后 $ a（x）=是$,

如果 $ q（x）=否$ 然后 $ a（x）=否$.

我可以简单地写 $ a（x）= q（x）$ 但是我以这种方式编写，以便我们可以将其与 $ mathsf {np} $.

$ mathsf {np} $ =有效算法的问题验证证明/证书/证人

有时我们不知道找到决策问题答案的任何有效方法，但是如果有人告诉我们答案并给我们一个证明我们可以有效核实通过检查证明以查看是否是一个，答案是正确的 有效证明。这是复杂性课背后的想法 $ mathsf {np} $.

如果证明太长了，这并不是真的有用，只需阅读证明，更不用说检查是否有效。我们希望验证所需的时间在原始输入的大小上是合理的，而不是给定证明的大小！这意味着我们真正想要的不是任意的长期证明，而是短的证明。请注意，如果验证者的运行时间是原始输入大小的多项式，则只能读取证明的多项式部分。所以短的我们的意思是 多项式大小.

每当我使用“证明”一词时，请在这一点上形成这一点。

这是我们的问题的示例 不知道 如何有效地解决，但我们可以有效地验证证据：

分割
输入： 一组有限的自然数 $ S $,
问题： 可以分区吗 $ S $ 分为两组 $ a $ 和 $ b $ ($ a cup b = s $ 和 $ a cap b = emptyset $)
这样的数字之和 $ a $ 等于数字的总和 $ b $ ($ sum_ {x in}} x = sum_ {x in B} x $)?

如果我给你 $ S $ 并询问您是否可以将其划分为两组，以使它们的总和相等，您不知道任何有效的算法可以解决它。您可能会尝试将数字划分为两组的所有可能方法，直到找到汇率相等的分区，或者在尝试所有可能的分区，而没有任何可能的分区。如果他们中的任何一个工作，您会说是的，否则您会拒绝。

但是这里有指数许多可能的分区，因此需要很多时间。但是，如果 我给你 两组 $ a $ 和 $ b $, ，您可以轻松检查总和是否相等 $ a $ 和 $ b $ 是一个分区 $ S $. 。请注意，我们可以有效地计算总和。

这对 $ a $ 和 $ b $ 我给你是一个是答案的证明。您可以通过查看我的证明并检查是否是 有效证明. 。如果答案是肯定的，那么有一个有效的证据，我可以给您，您可以有效地验证它。如果答案是否，则没有有效的证据。因此，无论我给您什么，您都可以检查并看到它不是有效的证据。我无法通过无效的证据欺骗您答案是肯定的。回想一下，如果证据太大，将需要很多时间来验证它，我们不希望发生这种情况，因此我们只关心 高效的 证明，具有多项式大小的IE证明。

有时人们会使用”证书“ 或者 ”见证“代替“证明”。

请注意，我为给定输入的答案提供了足够的信息 $ x $ 这样您就可以有效地找到并验证答案。例如，在我们的分区示例中，我不告诉您答案，我只给您一个分区，您可以检查它是否有效。请注意，您必须自己验证答案，您不能相信我的话。此外，您只能检查我的证明。如果我的证据有效，则意味着答案是肯定的。但是，如果我的证据无效不是意味着答案是否定的。您已经看到一个证据是无效的，不是没有有效的证据。我们正在谈论是的证据。我们不是在谈论否。

让我们看看一个例子：$ a = {2,4 } $ 和 $ b = {1,5 } $ 是证明$ s = {1,2,4,5 } $ 可以将相等的总和分为两组。我们只需要总结 $ a $ 和数字 $ b $ 并查看结果是否相等，并检查是否 $ a $, $ b $ 是分区 $ S $.

如果我给你 $ a = {2,5 } $ 和 $ b = {1,4 } $, ，您将检查并发现我的证明是无效的。这并不意味着答案是否定的，而只是意味着此特定的证据是无效的。您的任务是不是要找到答案，但仅检查您给出的证明是否有效。

这就像一个学生在考试中解决问题，并且教授检查答案是否正确。 :)（不幸的是，学生常常没有提供足够的信息来验证答案的正确性，教授必须猜测其余部分答案，并确定他们应该给学生的部分答案，的确很困难任务）。

令人惊讶的是，同样的情况适用于我们要解决的许多其他自然问题：我们可以有效核实如果给定的简短证明是有效的，但我们不知道任何有效的方法发现答案. 。这就是为什么复杂性课程的动力 $ mathsf {np} $ 是 非常有趣（尽管这不是定义它的原始动机）。无论您做什么（不仅在CS中，而且在数学，生物学，物理学，化学，经济学，管理，社会学，业务等方面，您都会面临落在此类中的计算问题。要了解有多少个问题 $ mathsf {np} $ 查看NP优化问题的汇编。确实，您将很难找到不在的自然问题 $ mathsf {np} $。这真是太神奇了。

$ mathsf {np} $ 是具有有效验证者的问题类, ， IE
有一个多项式时间算法可以验证给定的解决方案是否正确。

更正式的是，我们说一个决策问题 $ Q $ 在 $ mathsf {np} $ iff

有一个有效的算法 $ V $ 称为验证者
对于所有输入 $ x $,

如果 $ q（x）=是$ 然后有证据 $ y $ 这样 $ v（x，y）=是$,

如果 $ q（x）=否$ 然后所有证明 $ y $, $ v（x，y）=否$.

我们说验证者是声音如果答案是否定的，如果它不接受任何证据。换句话说，如果答案确实没有，则不能欺骗声音验证者接受证明。没有误报。

同样，我们说一个验证者是 完全的 如果答案是肯定的，则至少接受一个证明。换句话说，可以说服答案是肯定的。

术语来自逻辑和 证明系统。我们不能使用声音证明系统来证明任何错误的语句。我们可以使用完整的证明系统来证明所有真实的语句。

验证者 $ V $ 获得两个输入，

$ x $ ：原始输入 $ Q $, ，和
$ y $ ：建议的证明 $ q（x）=是$.

请注意我们想要 $ V $ 高效 $ x $. 。如果 $ y $ 是验证者能够阅读的大证据 仅一个多项式部分 的 $ y $. 。这就是为什么我们要求证明很短的原因。如果 $ y $ 简而言之 $ V $ 有效 $ x $ 与说 $ V $ 有效 $ x $ 和 $ y $ （因为大小 $ y $ 由固定多项式界定 $ x $).

总而言之，要证明一个决策问题 $ Q $ 在 $ mathsf {np} $ 我们必须给 高效的 验证算法是声音和 完全的.

历史注：历史上这不是原始定义 $ mathsf {np} $. 。原始定义使用所谓的 非确定性 图灵机。这些机器与任何相对应 实际的 机器模型，很难习惯（至少当您开始学习复杂性理论时）。我读到，许多专家认为他们会使用验证程序定义作为主要定义，甚至会命名该类 $ mathsf {vp} $ （在多项式时间内可验证）代替 $ mathsf {np} $ 如果他们回到计算复杂性理论的曙光。验证者的定义更自然，更易于理解概念，并且易于使用以显示问题 $ mathsf {np} $.

$ MATHSF {P} subseteq Mathsf {np} $

因此我们有$ mathsf {p} $=有效的解决 和 $ mathsf {np} $=有效验证. 。所以 $ mathsf {p} = mathsf {np} $ 如果IFF可以有效验证的问题与可以有效解决的问题相同。

请注意，任何问题 $ mathsf {p} $ 也在 $ mathsf {np} $, ，即如果您可以解决问题，也可以验证给定的证据是否正确：验证者将忽略证明！

那是因为我们不需要它，验证者可以单独计算答案，它可以决定答案是肯定还是否，没有任何帮助。如果答案是否，我们知道应该没有证据，我们的验证者只会拒绝所有建议的证据。如果答案是肯定的，应该一个证明，实际上，我们将接受任何证据。

我们本可以使我们的验证者只接受其中的一些，这也很好，只要我们的验证者接受至少一个证明验证者对问题的正常工作。

这是一个示例：

和
输入： 的清单 $ n+1 $ 自然数 $ a_1， cdots，a_n $, ，和 $ S $,
问题： 是 $ sigma_ {i = 1}^n a_i = s $?

问题在于 $ mathsf {p} $ 因为我们可以总结数字，然后将其与 $ S $, ，如果它们是平等的，我们还会返回是，如果不是。

问题也在 $ mathsf {np} $. 。考虑一个验证者 $ V $ 这将获得证明加总和的输入。它的作用与算法相同 $ mathsf {p} $ 我们在上面描述了。这是总和的有效验证器。

请注意，还有其他有效的验证符，其中一些可能会使用给出的证据。但是，我们设计的那个不是，这也很好。由于我们给出了一个高效的验证程序，因此问题出现在 $ mathsf {np} $. 。同样的技巧适用于所有其他问题 $ mathsf {p} $ 所以$ MATHSF {P} subseteq Mathsf {np} $.

蛮力/详尽的搜索算法 $ mathsf {np} $ 和 $ MATHSF {NP} subseteq Mathsf {exptime} $

最好的算法 我们知道 解决任意问题 $ mathsf {np} $ 是蛮力/详尽的搜索 算法。为问题选择有效的验证程序（通过我们的假设，它具有有效的验证器 $ mathsf {np} $）并一一检查所有可能的证据。如果验证者接受其中一个，那么答案是肯定的。否则答案是否定的。

在我们的分区示例中，我们尝试所有可能的分区，并检查其中任何一个的总和是否相等。

请注意，蛮力算法在最差的指数时间内运行。证明的大小在输入的大小中是多项式的。如果证明的大小是 $ m $ 然后有 $ 2^m $ 可能的证据。检查它们每个都会花费多项式时间。因此，总共蛮力算法需要指数时间。

这表明任何 $ mathsf {np} $ 问题可以在指数时间内解决，即$ MATHSF {NP} subseteq Mathsf {exptime} $. 。（此外，蛮力算法将仅使用多项式空间，即$ Mathsf {np} subseteq Mathsf {pspace} $ 但这是另一天的故事）。

一个问题 $ mathsf {np} $ 可以具有更快的算法，例如 $ mathsf {p} $ 具有多项式时间算法。但是对于任意问题 $ mathsf {np} $ 我们不知道可以做得更好的算法。换句话说，如果您只是告诉我您的问题已经存在 $ mathsf {np} $ （有关问题的其他内容）那么我们所知道的最快算法要解决，这需要指数时间。

但是，这并不意味着没有更好的算法，我们不知道. 。据我们所知，仍然有可能（尽管几乎所有复杂的理论家认为都不太可能）$ mathsf {np} = mathsf {p} $ 和所有 $ mathsf {np} $ 可以在多项式时间内解决问题。

此外，一些专家推测我们不能做得更好，即有问题 $ mathsf {np} $ 与需要达到指数时间的蛮力搜索算法相比，这不能更有效地解决。看到指数时间假设了解更多信息。但这没有证明，这只是一个推测。它只是显示了我们距离找到任意的多项式时间算法有多远 $ mathsf {np} $ 问题。

与指数时间的这种联系使某些人感到困惑：他们不正确地认为$ mathsf {np} $ 问题要求指数时间解决（甚至更糟糕的是，根本没有算法）。说一个问题正在 $ mathsf {np} $ 并不意味着一个问题是难的要解决，这只是意味着它是 简单的 要验证，这是一个上限关于解决问题的困难，许多 $ mathsf {np} $ 问题很容易解决 $ MATHSF {P} subseteq Mathsf {np} $.

但是，有 $ mathsf {np} $ 问题似乎难以解决。当我们讨论时，我会回到这个 $ mathsf {np} $-硬度。

下限似乎很难证明

好，所以我们现在知道许多自然问题那是 $ mathsf {np} $ 而且我们不知道解决它们的任何有效方法，我们怀疑它们确实需要指数时间来解决。我们可以证明这一点吗？

不幸的是证明的任务下限是很困难的。我们不能甚至证明这些问题需要超过 线性时间呢更不用说需要指数时间了。

证明线性时间下限非常容易：算法毕竟需要读取输入。证明超线性下限是一个完全不同的故事。我们可以证明超级线性下限，并且对我们正在考虑的算法的类型有更多的限制，例如使用比较对算法进行分类，但是我们不知道没有这些限制的较低限制。

为了证明问题的上限，我们只需要设计足够好的算法即可。它通常需要知识，创造性的思维甚至创造力才能提出这样的算法。

但是，与证明下限相比，该任务要简单得多。我们必须证明 没有好算法. 。不是我们没有了解现在任何足够好的算法，但是 没有任何好算法, ，那 没有人会提出好算法. 。如果您以前没有，请考虑一下一分钟，我们如何显示这样的 不可能的结果?

这是人们感到困惑的另一个地方。这里的“不可能”是 数学上的不可能, ，即，将来有些天才可以解决并不是我们这并不是一件短暂的事情。当我们说不可能的时候，我们意味着这绝对是不可能的，就像不可能 $1=0$. 。没有科学进步可以使它成为可能。当我们证明下限时，这就是我们正在做的事情。

为了证明下限，即证明一个问题需要一定时间解决，这意味着我们必须证明任何算法，即使是尚不了解的算法，也无法更快地解决问题。我们知道许多聪明的想法（贪婪，匹配，动态编程，线性编程，半决赛编程，平方之和的编程和许多其他智能的想法），我们还不知道更多。排除一种算法或设计算法的一种特殊想法是不够的，我们需要排除所有这些算法，即使是我们尚不了解的那些，即使是那些可能永远都不知道的人！并且可以将所有这些结合在算法中，因此我们还需要排除它们的组合。已经取得了一些进展，表明某些想法无法解决困难 $ mathsf {np} $ 问题，例如贪婪及其扩展无法正常工作，并且有一些与动态编程算法有关的工作，并且在使用线性编程的特定方式上有一些工作。但是，这些甚至还没有排除我们知道的智能想法（如果您有兴趣，请在限制的计算模型中寻找较低的想法）。

障碍：下限是很难证明

另一方面，我们有数学结果称为障碍也就是说，下层的证据不能如此，这样几乎涵盖了我们用来证明下限的所有技术！实际上，在亚历山大·拉兹巴罗夫（Alexander Razbarov）和史蒂文·鲁迪奇（Steven Rudich）的自然证明障碍结果。事实证明，特定类型的较低的证据的存在将暗示加密伪数字生成器和许多其他加密工具的不安全感。

我说几乎是因为近年来，主要取得了一些进展瑞安·威廉姆斯这已经能够明智地绕过障碍结果，到目前为止，结果仍然是非常弱的计算模型，而不是排除一般多项式时间算法。

但是我在分歧。我要提出的要点是，证明下限很困难，我们对通用算法的解决方案没有强大的下限 $ mathsf {np} $ 问题。

另一方面，瑞安·威廉姆斯（Ryan Williams）的作品表明，在证明下限和证明上限之间存在密切的联系。看他在ICM 2014上的演讲如果你感兴趣。

减少：使用另一个问题作为子例程/甲骨文/黑匣子解决问题

减少的想法非常简单：解决问题，请使用算法解决另一个问题。

这是简单的示例：假设我们要计算 $ n $ 自然数，我们有算法 $ sum $ 这返回两个给定数字的总和。我们可以使用吗？ $ sum $ 要加总列表中的数字？当然！

问题：

输入：列表 $ n $ 自然数 $ x_1， ldots，x_n $,
输出：返回 $ sum_ {i = 1}^{n} x_i $.

还原算法：

$ s = 0 $

为了 $ i $ 从 $1$ 至 $ n $
2.1. $ s = sum（s，x_i）$

返回 $ S $

我们在这里使用 $ sum $ 在我们的算法中 子例程. 。请注意，我们不在乎如何 $ sum $ 作品，就像 黑盒子 对我们来说，我们不在乎里面发生了什么 $ sum $. 。我们经常指子例程 $ sum $ 作为 Oracle. 。它像是德尔菲的甲骨文在希腊神话中，我们提出问题，甲骨文回答了它们，我们使用答案。

从本质上讲，这是一个减少的是：假设我们有问题的算法，并将其用作解决另一个问题的甲骨文。在这里有效意味着有效假设Oracle在时间单位中答案，即我们计算Oracle的每个执行一个步骤。

如果Oracle返回一个很大的答案，我们需要阅读它，这可能需要一些时间，因此我们应该计算时间我们阅读Oracle给我们的答案。同样，要从Oracle编写/询问问题。但是Oracle立即起作用，即，一旦我们从Oracle提出问题时，Oracle就会在一个时间单位中为我们编写答案。 Oracle所做的所有工作都是一个步骤，但这排除了我们编写问题并阅读答案所花费的时间。

因为我们不在乎甲骨文的工作原理，而只关心它所返回的答案，我们才能简化，并将甲骨文视为问题本身代替算法。换句话说，我们不在乎Oracle是否不是算法，我们不在乎Oracles如何提出其答复。

例如，$ sum $ 在上面的问题中是添加函数本身（不是用于添加计算的算法）。

我们可以从甲骨文中提出多个问题，并且不需要预先确定这些问题：我们可以提出一个问题，并基于答案：甲骨文返回我们自己执行一些计算，然后根据我们得到的答案提出另一个问题上一个问题。

查看这一点的另一种方式是将其视为 交互式计算. 。交互式计算本身就是大型主题，因此我不会在这里介绍它，但是我认为提到这种减少的观点可能会有所帮助。

算法 $ a $ 使用Oracle/黑匣子 $ o $ 通常表示为 $ a^o $.

我们上面讨论的还原是减少的最一般形式，被称为 减少黑盒（又名 减少甲骨文, 简化图灵).

更正式：

我们说这个问题 $ Q $ 黑盒可简化为问题 $ o $ 和写 $ q leq_t o $ iff
有算法 $ a $ 因此对于所有输入 $ x $,
$ q（x）= a^o（x）$.

换句话说，如果有算法 $ a $ 使用Oracle $ o $ 作为子例程并解决问题 $ Q $.

如果我们的还原算法 $ a $ 在多项式时间里运行我们称之为 多项式时间黑盒还原 或只是一个 减少厨师（为了纪念Stephen A. Cook）和写 $ q leq^ mathsf {p} _t o $。（下标 $ t $ 代表“图灵”以纪念艾伦·图灵（Alan Turing）).

但是，我们可能想对减少算法与Oracle相互作用的方式进行一些限制。研究了几个限制，但最有用的限制是称为 多一减少（又名 映射减少).

这里的想法是给定输入 $ x $, ，我们执行一些多项式时间计算并生成A $ y $ 这是Oracle解决的问题的实例。然后，我们询问Oracle并将其返回答案返回给我们。我们被允许从Oracle提出一个问题，Oracle的答案就是将返回的问题。

更正式，

我们说这个问题 $ Q $ 多个可以减少问题 $ o $ 和写 $ q leq_m o $ iff
有算法 $ a $ 因此对于所有输入 $ x $,
$ q（x）= o（a（x））$.

当还原算法是多项式时间时，我们称之为多项式时间多一减少 或简单 减少KARP （为了纪念理查德·卡普（Richard M. Karp））并用它表示 $ q leq_m^ Mathsf {p} o $.

对这种特定非交互减少的兴趣的主要原因是它保留了 $ mathsf {np} $ 问题：如果问题从一个多项式时间降低了 $ a $ 到一个 $ mathsf {np} $ 问题 $ b $, ，然后 $ a $ 也在 $ mathsf {np} $.

简单的减少概念是复杂性理论中最基本的概念之一 $ mathsf {p} $, $ mathsf {np} $, ，和 $ mathsf {np} $-Complete（我们将在下面讨论）。

该帖子已经太长了，超过了答案的限制（30000个字符）。我将继续答案第二部分.

其他提示

第二部分

继续第一部分.

上一个超过答案（30000）中允许的最大字母数量，因此我将其分为一分。

$ mathsf {np} $ - 完整性：普遍的 $ mathsf {np} $问题

好的，到目前为止，我们已经讨论了有效解决问题的类别（$ Mathsf {p} $）和有效验证的问题类（$ Mathsf {np} $）。正如我们在上面讨论的那样，这两个都是上限. 。让我们现在将注意力集中在$ mathsf {np} $内部的问题上，令人惊讶的是，许多自然问题都在$ mathsf {np} $内部。

现在有时我们想说 问题很难解决. 。但是正如我们上面提到的那样，我们不能为此目的使用较低的距离：从理论上讲，它们正是我们想要证明的，但是实际上，我们在证明下限方面并不是很成功，总的来说，它们很难正如我们提到的那样很难证明以上。还有一种方法可以说 问题很难解决?

这是$ mathsf {np} $ - 完整性的概念。但是，在定义$ mathsf {np} $之前 - 完整性让我们再次查看减少。

减少相对困难

我们可以想到 较低的人是绝对困难 问题。然后我们可以想到 减少作为相对难度的 问题。我们可以接受 从$ a $ $ a $ b $还原 就像说 $ a $比$ b $容易. 。这是我们用于减少的$ leq $概念中隐含的。正式地，减少给出了有关问题的部分命令。

如果我们可以有效地将问题$ a $减少到另一个问题$ b $，那么$ a $不应该比$ b $更难解决。直觉如下：

让$ m^b $是从$ a $降至$ b $的有效降低，即$ m $是一种使用$ b $并解决$ a $的有效算法。让$ n $是解决$ b $的有效算法。我们可以将有效的降低$ m^b $和有效算法$ n $结合起来，以获取$ m^n $，这是一种解决$ a $的有效算法。

这是因为我们可以在有效的算法中使用有效的子例程（每个子例程呼叫的时间为一个时间单位），结果是有效的算法。这是多项式时间算法和$ mathsf {p} $的非常好的封闭属性，它不适合许多其他复杂性类。

$ MATHSF {NP} $ - 完成表示最困难的$ Mathsf {np} $问题

现在，我们有一种比较问题难度的相对方法，我们可以询问$ Mathsf {np} $中哪些问题最困难？我们称之为这样的问题 $ mathsf {np} $ - 完成.

$ mathsf {np} $ - 完整的问题是最困难的$ mathsf {np} $问题,
如果我们可以有效地解决$ mathsf {np} $ - 我们可以有效地解决所有$ mathsf {np} $问题。

更正式的是，我们说决策问题$ a $ as $ mathsf {np} $ - 完成IFF

$ a $ ins $ mathsf {np} $，并且
对于所有$ mathsf {np} $问题$ b $，$ b $是多项式时间多，可还原为$ a $（$ b leq_m^ mathsf {p} a $）。

考虑$ mathsf {np} $ - 完整问题的另一种方法是将它们视为复杂性版本通用图灵机. 。 $ mathsf {np} $ - 完整的问题是 普遍的 在$ mathsf {np} $中，问题在类似的意义上：您可以使用它们来求解任何$ mathsf {np} $问题。

这是好的原因之一卫星赛车很重要，尤其是在行业中。 SAT是$ Mathsf {np} $ - 完整（稍后再详细介绍），因此我们可以专注于设计非常好的算法（尽可能多）来求解SAT。为了解决$ Mathsf {np} $中的任何其他问题，我们可以将问题实例转换为SAT实例，然后使用工业质量高度优化的SAT-Solver。

（许多人都在为他们在行业中实用使用的其他两个人致力于优化其算法的问题是整数编程和约束满意度问题。取决于您的问题以及您关心其中一种的优化算法的实例，可能比其他算法更好。）

如果一个问题满足$ mathsf {np} $的定义中的第二个条件 - 完整性（即通用条件）
我们称问题为 $ mathsf {np} $ - 硬.

$ mathsf {np} $ - 硬度是说问题很困难的一种方式。

我个人更喜欢考虑$ mathsf {np} $ - 硬度作为普遍性，所以可能 $ mathsf {np} $ - 通用 本来可以是一个更正确的名称，因为目前我们不知道它们是否真的很难，或者仅仅是因为我们无法为他们找到多项式时间算法）。

名称$ mathsf {np} $ - 难以混淆人们错误地认为$ mathsf {np} $ - 硬问题是问题 绝对地 难以解决。我们还不知道，我们只知道他们是 与任何$ mathsf {np} $问题一样困难 解决。尽管专家认为所有$ mathsf {np} $问题仍然不可能容易且有效地解决。换句话说，与任何其他$ mathsf {np} $问题一样困难并不意味着很困难。只有在有$ mathsf {np} $问题的情况下才是正确的 绝对地 硬（即没有任何多项式时间算法）。

现在的问题是：

是否有任何$ mathsf {np} $ - 完整的问题？
我们知道他们一个吗？

当我们讨论卫星赛车手时，我已经给出了答案。令人惊讶的是，许多天然$ mathsf {np} $问题被证明为$ mathsf {np} $ - 完成（稍后再详细介绍）。因此，如果我们在$ mathsf {np} $中选择一个随机选择的自然问题，则可能是我们知道它的多项式时间算法，或者我们知道它是$ sathsf {np} $ - 完全的。自然问题的数量都不是很小（一个重要的例子是考虑整数，请参阅此列表对于类似问题的列表）。

在转到$ mathsf {np} $的示例之前，请注意，我们可以为其他复杂性类提供类似的定义，并定义复杂性类，例如$ mthsf {exptime} $ - 完整。但是，正如我所说，$ mathsf {np} $有一个非常特殊的位置：与$ mathsf {np} $不同，其他复杂性课程几乎没有天然完整问题。

（通过自然问题，我的意思是人们真正关心解决的问题，而不是人们人为地定义的问题以证明某种观点。我们可以以基本相同的问题来修改任何问题，例如，我们可以更改回答输入$ p lor lnot p $ sat n no no。我们可以以类似的方式定义许多明显的问题，而不会基本上改变问题。但是谁会真正关心这些人造问题？）

$ mathsf {np} $ - 完整问题：$ mathsf {np} $中存在通用问题

首先，请注意，如果$ a $是$ mathsf {np} $ - 硬和$ a $ polyenmial time多一减少至$ b $，那么$ b $也是$ m m缩短的，也是$ mathsf {np} $ - 硬。我们可以使用$ a $解决任何$ mathsf {np} $问题，我们可以使用$ b $解决$ a $本身，因此我们可以使用$ b $解决任何$ mathsf {np} $问题！

这是一个非常有用的引理。如果我们想证明一个问题是$ mathsf {np} $ - 我们很难证明我们可以减少所有$ mathsf {np} $问题，这并不容易，因为我们对这些问题一无所知比那个$ mathsf {np} $。

考虑一下一秒钟。我们第一次看到这个真是太神奇了。我们可以证明所有$ mathsf {np} $问题是SAT可减少的，而无需了解这些问题，除了它们在$ Mathsf {np} $中！

幸运的是，我们不需要多次执行此操作。一旦我们显示出一个问题，例如$ sat $ as $ mathsf {np} $ - 对于其他问题，我们只需要减少$ sat $。例如，要证明$ subsetsum $是$ mathsf {np} $ - 难以将$ SAT $减少到$ subsetsum $。

好的，让我们展示有一个$ mathsf {np} $ - 完整问题。

通用验证者是$ m athsf {np} $ - 完成

笔记： 以下部分在第一读中可能有些技术。

第一个示例有点人为，但我认为它对直觉更简单和有用。回想$ mathsf {np} $的验证者定义。我们想定义一个可以用来解决所有问题的问题。那么，为什么不定义问题呢？

时间限制的通用验证者
输入：获得输入和证明，输入$ x $的算法$ v $的代码以及两个数字$ t $和$ k $。
输出：$是$，如果最多有尺寸证明$ k $ st，则被$ v $用于输入$ x $ in $ t $ steps中的$ v $，如果没有这样的证明，则$ no $。

显示这个问题并不难我称为$ univer $ is $ mathsf {np} $ - 硬：

在$ mathsf {np} $中使用验证者$ v $。要检查给定输入$ x $的证据，我们将$ v $的代码和$ x $传递给$ UNIVER $。
（$ t $和$ k $是$ v $的运行时间和我们正在寻找$ x $的证据的上限。我们需要它们限制$ v $的运行时间和大小多项式的证明，大小为$ x $。）

（技术详细信息：运行时间将在$ t $中是多项式，我们想让输入的大小至少为$ t $，因此我们给出$ t $ in Unary note，而不是二进制。类似的$ k $在Unary中给出）

我们仍然需要证明问题本身在$ mathsf {np} $中。要显示$ univer $在$ mathsf {np} $中，我们考虑以下问题：

时间限制的口译员
输入：算法$ m $的代码，$ m $的输入$ x $和数字$ t $。
输出：$ YES $如果算法$ M $给定输入$ x $ returns $是$ t $ step，$ no $如果不返回$ t $ steps $ yes $ yes $ $。

您可以将算法大致认为是$ c $程序的代码。不难看到此问题是在$ mathsf {p} $中。从本质上讲，它是编写解释器，计算步骤的数量，并在$ t $步骤后停止。

我将在此问题中使用缩写$解释器$。

现在，不难看到$ univer $在$ mathsf {np} $中：给定输入$ m $，$ x $，$ t $和$ k $;和建议的证明$ c $；检查$ c $是否最多有$ k $的大小，然后使用$解释器$查看$ m $ returns $是$ x $上的$是$ x $和$ c $ in $ t $ steps。

$ sat $ is $ mathsf {np} $ - 完成

通用验证者$ UNIVER $有点人造。显示其他问题是$ mathsf {np} $ - 硬。从$ univer $中减少比从任意$ mathsf {np} $问题减少的要容易得多。我们需要更简单的问题。

从历史上看，第一个自然问题被证明是$ m m iathsf {np} $ - 完整是 $ sat $.

回想一下，$ sat $是我们得到命题公式的问题，我们想看看它是否是 令人满意, ，即，如果我们可以为命题变量分配true/fals，以使其评估为true。

坐着
输入：命题公式$ varphi $。
输出：$是$如果$ varphi $满足，则$否$如果不是$。

不难看到$ sat $在$ mathsf {np} $中。我们可以在多项式时间内评估给定真相分配的给定命题公式。验证者将获得真理分配，并将评估该真相分配的公式。

写...

SAT是$ Mathsf {np} $ - 硬

$ mathsf {np} $ - 练习的完整性意味着什么？

如果你该怎么办必须解决$ mathsf {np} $ - 完整问题？

$ mathsf {p} $ vs. $ mathsf {np} $

下一步是什么？然后去哪儿？

不仅有用的答案，我建议您高度观看 ”超越计算：P与NP问题“ 经过 迈克尔·史佩尔（Michael Sipser）. 。我认为该视频应该被存档为计算机科学领域的主要教学视频之一。

享受！

将我的答案复制到堆栈溢出上的类似问题：

解释pv。NP等技术的最简单方法是将“单词问题”与“多项选择问题”进行比较。

当您尝试解决“单词问题”时，您必须从头开始找到解决方案。当您试图解决“多项选择问题”时，您可以选择：要么解决“单词问题”，要么尝试插入给您的每个答案，并选择适合的候选人答案。

通常情况下，“多项选择问题”比相应的“单词问题”要容易得多：替换候选人答案并检查它们是否合身可能需要的努力明显少于从头开始找到正确的答案。

现在，如果我们同意需要多项式时间“简单”的努力，那么P级将由“简单的单词问题”组成，并且NP类将包括“简单的多项选择问题”。

第v。np的本质是一个问题：“是否有任何简单的多项选择问题像单词问题一样容易”？也就是说，是否有问题很容易验证给定答案的有效性，但是从头开始找到答案很困难？

现在，我们直观地了解NP是什么，我们必须挑战我们的直觉。事实证明，从某种意义上说，有“多项选择问题”，其中最困难：如果人们能找到解决方案之一，那就是“最困难的所有问题”，人们将能够找到解决所有问题的解决方案NP问题！当库克发现这40年前时，这完全是一个惊喜。这些“最困难的”问题被称为NP-HARD。如果您找到其中一个的“单词问题解决方案”，您会自动为每个“简单的多项选择问题”找到一个“单词问题解决方案”！

最后，NP完整问题是那些同时是NP和NP-HARD的问题。遵循我们的类比，它们同时“像多项选择问题一样容易”，并且“最困难的都是单词问题”。

其中最简单的是P，在多项式时间中可以解决的问题属于这里。

然后是NP。在此非确定性图灵机上的多项式时间中可以解决的问题属于这里。

硬度和完整性必须减少。一个问题是难的对于C类，如果C中的每个问题都还原为A。如果问题A为 很难NP, 或NP-HARD，如果NP中的每个问题都减少到A。

最后，一个问题是 完全的 对于C类在 C和难的对于C.就您而言，问题A是 完成NP, ，或NP完整的，如果NP中的每个问题都还原为A，而A为NP。

为了补充NP的解释，当且仅当可以在（确定性）多项式时间中验证解决方案时，NP出现问题。考虑您知道的任何NP完整问题，SAT，集团，子集总和，顶点封面等。如果您“获取解决方案”，则可以在多项式时间内验证其正确性。它们是变量的真理分配，完整的子图，数字子集和主导所有边缘的顶点集。

来自 P vs. NP和计算复杂性动物园视频。

适用于具有真的很大问题的版本...

P问题

简单的 解决（Rubix Cube）

NP问题

难的解决 - 但是检查答案是 简单的 （数独）

也许这些都是真正的问题，但我们不知道... p vs. np.

NP完整

许多NP问题归结为同一问题（Sudoku是列表的新来者）。

EXP问题

真的很难 解决（例如，国际象棋中的最佳下一个举动）

NP硬性问题

NP-HARD在视频中没有很好地解释（这是下图中的所有粉红色位）。维基百科 np-hard Euler图对此更清晰。

图表

如视频末尾所示。

p, NP, NP完整 和 np-hard 是复杂性类别，根据解决方案的算法复杂性对问题进行分类。简而言之，它们基于三个属性：

在多项式时间内可解决： 定义决策问题，可以通过确定性的图灵机（DTM）使用多项式量的计算时间来解决，即，其运行时间在算法的输入大小中受多项式表达式的上限。使用Big-O符号这个时间的复杂性定义为 O(n ^ k), ，其中n是输入和ka常数系数的大小。

在多项式时间内可验证的解决方案： 定义决策问题，即使获得正确的解决方案可能需要更高的时间，也可以使用多项式计算时间通过DTM来验证给定解决方案。

减少多项式时间中的任何NP问题: ：定义决策问题，其解决方案的算法可用于在多项式时间翻译步骤之后解决任何NP问题。

我最近写了一篇有关该主题的文章，提供了更多详细信息，包括将NP问题减少到NP-HARD问题的代码演示：复杂性类别的问题

许可以下： CC-BY-SA 和归因

不隶属于 cs.stackexchange