258

P=NP 是否是计算机科学中最著名的问题。这是什么意思？为什么它如此有趣？

哦，为了获得额外的荣誉，请张贴一份声明的真假证明。:)

4

6 回答 6

401

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

定义：

  • 多项式时间意味着算法的复杂度为 O(n^k)，其中 n 是数据的大小（例如要排序的列表中的元素数），k 是常数。

  • 复杂性是用操作次数来衡量的时间，它是数据项数量的函数。

  • 操作是对特定任务有意义的基本操作。对于排序，基本操作是比较。对于矩阵乘法，基本运算是两个数的乘法。

现在的问题是，确定性与非确定性是什么意思？有一个抽象的计算模型，一种称为图灵机 (TM) 的假想计算机。这台机器有有限数量的状态和一个无限的磁带，它有离散的单元，可以在其中写入和读取有限的符号集。在任何给定时间，TM 都处于其中一种状态，它正在查看磁带上的特定单元格。根据它从该单元格读取的内容，它可以将一个新符号写入该单元格，将磁带向前或向后移动一个单元格，然后进入不同的状态。这称为状态转换。令人惊奇的是，通过仔细构造状态和转换，您可以设计一个 TM，它相当于任何可以编写的计算机程序。

这里有两种与我们有关的 TM：确定性和非确定性。对于从磁带上读取的每个符号，确定性 TM 只有一个从每个状态的转换。一个非确定性的 TM 可能有几个这样的转变，即它能够同时检查几个可能性。这有点像产生多个线程。不同之处在于，非确定性 TM 可以根据需要生成任意数量的此类“线程”，而在真实计算机上一次只能执行特定数量的线程（等于 CPU 的数量）。实际上，计算机基本上是带有有限磁带的确定性 TM。另一方面，非确定性 TM 无法在物理上实现，除非使用量子计算机。

已经证明，任何可以由非确定性 TM 解决的问题都可以由确定性 TM 解决。但是，尚不清楚需要多长时间。陈述 P=NP 意味着如果一个问题在非确定性 TM 上花费多项式时间，那么人们可以构建一个确定性 TM，它也可以在多项式时间内解决相同的问题。到目前为止，没有人能够证明它可以做到，但也没有人能够证明它不能做到。

NP 完全问题是指一个 NP 问题 X，这样任何 NP 问题 Y 都可以通过多项式归约化为 X。这意味着，如果有人提出了 NP 完全问题的多项式时间解决方案，那么这也将为任何 NP 问题提供多项式时间解决方案。因此，这将证明 P = NP。相反，如果有人要证明 P!=NP，那么我们可以肯定在传统计算机上没有办法在多项式时间内解决 NP 问题。

NP 完全问题的一个例子是寻找一个真值赋值的问题，该赋值将使包含 n 个变量的布尔表达式为真。
目前在实践中，任何在非确定性 TM 上花费多项式时间的问题只能在确定性 TM 或传统计算机上以指数时间完成。
例如，解决真值分配问题的唯一方法是尝试 2^n 种可能性。

于 2008-09-24T15:20:00.857 回答
96
  1. 如果可以在多项式时间内计算答案，则在P（P多项式时间）中存在是或否问题。
  2. 如果可以在多项式时间内验证是的答案，则在NP（N个确定性多项式时间）中是或否问题。

直观地，我们可以看到，如果问题在P中，那么它在NP中。给定P中问题的潜在答案，我们可以通过简单地重新计算答案来验证答案。

不太明显，也更难回答的是，是否NP中的所有问题都在P中。我们可以在多项式时间内验证答案这一事实是否意味着我们可以在多项式时间内计算该答案？

有大量重要的问题已知是NP 完全的（基本上，如果任何这些问题被证明在P中，那么所有 NP问题都被证明在P中）。如果P = NP，那么所有这些问题都将被证明具有有效的（多项式时间）解。

大多数科学家认为P != NP。但是，尚未为P = NP 或P != NP建立证据。如果有人为任一猜想提供证明，他们将赢得 100 万美元。

于 2008-09-24T17:03:31.793 回答
24

给出我能想到的最简单的答案：

假设我们有一个需要一定数量的输入的问题，并且有各种潜在的解决方案，对于给定的输入，这些解决方案可能会也可能不会解决问题。谜题杂志中的逻辑谜题就是一个很好的例子：输入是条件（“乔治不住在蓝色或绿色的房子里”），潜在的解决方案是一个陈述列表（“乔治住在黄色的房子里”）房子，种豌豆，养狗”）。一个著名的例子是旅行推销员问题：给定一个城市列表，以及从任何城市到达任何其他城市的时间，以及时间限制，一个潜在的解决方案是按照推销员访问城市的顺序列出城市列表，以及如果旅行时间的总和小于时间限制，它将起作用。

如果我们可以有效地检查潜在的解决方案以查看它是否有效，那么这样的问题就存在于 NP 中。例如，给定一个销售人员按顺序访问的城市列表，我们可以将每次城市之间的旅行时间相加，并轻松查看是否在时间限制内。如果我们能够有效地找到解决方案（如果存在），那么问题就在 P 中。

（有效地，在这里，有一个精确的数学含义。实际上，这意味着大问题不会不合理地难以解决。在寻找可能的解决方案时，一种低效的方法是列出所有可能的潜在解决方案，或类似的东西，而一种有效的方法需要搜索更有限的集合。）

因此，P=NP 问题可以这样表达：如果您可以有效地验证上述问题的解决方案，您能否有效地找到解决方案（或证明没有解决方案）？显而易见的答案是“你为什么能做到？”，这就是今天的问题所在。没有人能够以一种或另一种方式证明这一点，这让很多数学家和计算机科学家感到困扰。这就是为什么任何能够证明该解决方案的人都会从 Claypool 基金会获得 100 万美元。

我们通常假设 P 不等于 NP，即没有找到解决方案的通用方法。如果结果证明 P=NP，很多事情都会改变。例如，密码学将变得不可能，随之而来的是互联网上的任何隐私或可验证性。毕竟，我们可以有效地获取加密文本和密钥并生成原始文本，因此如果 P=NP 我们可以在事先不知道密钥的情况下有效地找到密钥。密码破解将变得微不足道。另一方面，我们可以有效地解决各类规划问题和资源分配问题。

你可能听说过 NP-complete 的描述。一个 NP 完全问题（当然）是一个 NP 问题，并且具有这个有趣的性质：如果它在 P 中，那么每个 NP 问题都是，所以 P=NP。如果你能找到有效解决旅行推销员问题的方法，或者从谜题杂志中找到逻辑谜题，你就可以有效地解决 NP 中的任何问题。NP 完全问题在某种程度上是最难的 NP 问题。

所以，如果你能为任何 NP 完全问题找到一种有效的通用解技术，或者证明不存在这样的问题，那么名利就是你的了。

于 2008-09-24T16:26:16.453 回答
9

根据我的拙见做一个简短的总结：

有一些简单的计算问题（比如在图中找到两点之间的最短路径），计算速度非常快（ O(n^k)，其中 n 是输入的大小，k 是常数（在图的情况下，它是顶点或边的数量））。

其他问题，例如找到穿过图中每个顶点的路径或从公钥中获取 RSA 私钥更难 (O(e^n))。

但是 CS 说问题在于我们不能将非确定性图灵机“转换”为确定性图灵机，但是我们可以将非确定性有限自动机（如正则表达式解析器）转换为确定性自动机（好吧，你可以，但是机器的运行时间会很长）。也就是说，我们必须尝试所有可能的路径（通常聪明的 CS 教授可以排除一些路径）。

这很有趣，因为甚至没有人知道解决方案。有人说是真的，有人说是假的，但没有达成共识。另一个有趣的事情是，解决方案会对公钥/私钥加密（如 RSA）有害。您可以像现在生成 RSA 密钥一样轻松破解它们。

这是一个非常鼓舞人心的问题。

于 2008-09-21T16:14:21.843 回答
6

对于问题的 P=?NP 部分的内容和原因，我没有什么可以补充的，但关于证明。一个证明不仅值得一些额外的功劳，而且还可以解决一个千年问题。最近进行了一项有趣的民意调查，就证明的主题而言，公布的结果 (PDF)绝对值得一读。

于 2008-09-24T15:26:28.127 回答
5

首先，一些定义：

  • 如果您可以在比n^ksome更短的时间内计算出解决方案，则 P 中存在一个特定问题k，其中n是输入的大小。例如，可以在n log n小于 的情况下进行n^2排序，因此排序是多项式时间。

  • 如果存在k这样一个问题，即存在一个至多存在一个大小的解决方案n^k，您最多可以及时验证n^k。对图进行 3 着色：给定一个图，3 着色是具有大小的（顶点，颜色）对的列表，O(n)您可以及时O(m)（或O(n^2)）验证所有邻居是否具有不同的颜色。因此，仅当存在简短且易于验证的解决方案时，图才可进行 3 色着色。

NP 的一个等效定义是“在多项式时间内可以由 N 非确定性图灵机解决的问题” 。虽然这会告诉您名称的来源，但它并不能让您直观地感受到 NP 问题是什么样的。

请注意，P 是 NP 的子集：如果您可以在多项式时间内找到一个解，那么就有一个可以在多项式时间内验证的解——只需检查给定的解是否等于您可以找到的解。

为什么这个问题P =? NP很有趣？要回答这个问题，首先需要了解什么是 NP 完全问题。简单地说，

  • 如果 (1) L 在 P 中，并且 (2) 解决 L 的算法可用于解决 NP 中的任何问题 L'，则问题 L 是 NP 完全的；也就是说，给定 L' 的实例，当且仅当 L' 的实例有解时，您才能创建具有解的 L 的实例。形式上讲，NP 中的每个问题 L' 都可以归约为 L。

请注意，L 的实例必须是多项式时间可计算的，并且具有多项式大小，大小为 L'；这样，在多项式时间内解决一个 NP 完全问题为我们提供了所有NP 问题的多项式时间解决方案。

这是一个例子：假设我们知道图的 3 色是一个 NP 难题。我们想证明决定布尔公式的可满足性也是一个 NP 难题。

对于每个顶点 v，有两个布尔变量 v_h 和 v_l，以及要求（v_h 或 v_l）：每一对只能有值 {01,10,11}，我们可以将其视为颜色 1、2 和 3。

对于每条边 (u, v)，要求 (u_h, u_l) != (v_h, v_l)。那是，

not ((u_h and not u_l) and (v_h and not v_l) or ...) 列举所有相等的配置并规定它们都不属于这种情况。

AND' 将所有这些约束加在一起给出了一个具有多项式大小 ( O(n+m)) 的布尔公式。您可以检查计算是否也需要多项式时间：您正在为O(1)每个顶点和每个边做简单的事情。

如果你能解决我做的布尔公式，那么你也可以解决图形着色：对于每对变量 v_h 和 v_l，让 v 的颜色与这些变量的值匹配。通过公式的构造，邻居不会有相同的颜色。

因此，如果图的 3 色是 NP 完全的，那么布尔公式可满足性也是如此。

我们知道图的 3 着色是 NP 完全的；然而，从历史上看，我们通过首先展示布尔电路可满足性的 NP 完备性，然后将其减少到 3-colorability（而不是相反）来知道这一点。

于 2009-02-11T07:26:45.187 回答