“P=NP”是什么？为什么它是一个著名的问题？

Question

“P=NP”是什么？为什么它是一个著名的问题？

computer-sciencetheorycomplexity-theorynp-completep-np

270

“P=NP”问题或许是计算机科学中最著名的问题。它意味着什么？为什么如此有趣？

顺便提一句，如果能够证明这个命题的真假，会非常有价值哦。 :)

- raldi

20

正如 MIT 的 Scott Aaronson 所指出的那样："如果 P = NP，那么世界将会比我们通常认为的大不相同。创新突破就没有特殊价值，解决问题和发现解决方案之间也不存在根本性差异。每个欣赏交响乐的人都会成为莫扎特；每个能够遵循逐步论证的人都会成为高斯......" 摘自 http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP 。 - gts

3

请参阅[在基本术语中，P、NP、NP-Complete和NP-Hard的定义是什么？]（http://cs.stackexchange.com/questions/9556/in-basic-terms-what-is-the-definition-of-p-np-np-complete-and-np-hard）在[cs.se]上。 - Kaveh

6个回答

104

若一个问题的答案可以在多项式时间内计算，则该问题是P（多项式时间）问题。
若能够在多项式时间内验证问题的答案，则该问题是NP（非确定性多项式时间）问题。

直观地说，如果一个问题属于P，那么它也属于NP。对于P问题的潜在答案，我们可以通过重新计算该答案来验证答案。

不太明显，也更难回答的问题是，是否所有属于NP的问题都属于P。能否在多项式时间内验证答案意味着能否在多项式时间内计算该答案？

许多重要问题被证明为NP-完全问题（基本上，如果这些问题中的任何一个被证明属于P，那么所有NP问题均被证明属于P）。如果P=NP，那么所有这些问题都将被证明具有高效（多项式时间）解决方案。

大多数科学家认为P！= NP。然而，目前没有为P=NP或P！=NP的任何一个猜想提供证明。如果有人为任何一个猜想提供了证明，他们将赢得100万美元的千禧年大奖。

- Derek Park

24

简单回答一下：

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

如果我们可以有效地检查潜在解决方案是否有效，则此类问题属于NP。例如，给定推销员按顺序访问的城市列表，我们可以计算每个城市之间的旅行时间总和，并轻松查看是否符合时间限制。如果我们可以有效地找到一个解决方案，那么该问题就属于P。

因此，如果你能够有效地验证上述类型问题的解决方案，那么你能否有效地找到解决方案（或证明不存在解决方案）呢？显然的答案是“为什么你能够做到？” 这就是今天该问题的现状。没有人能够证明它是否成立，这让许多数学家和计算机科学家感到困扰。这就是为什么任何能够证明这个问题的人都可以得到Claypool基金会一百万美元奖励的原因。

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

您可能听说过NP完全的描述。 NP完全问题是一个NP问题（当然），并具有这种有趣的属性：如果它在P中，则每个NP问题都在其中，因此P=NP。如果您能够找到一种有效的方法来解决旅行推销员问题或来自谜题杂志的逻辑谜题，您可以有效地解决NP中的任何问题。 NP完全问题从某种意义上说是最难的NP问题。

因此，如果您可以为任何NP完全问题找到有效的一般解决技术，或证明不存在这样的技术，则您将获得声誉和财富。

- David Thornley

1

在你倒数第二段中，你说“某种程度上来说，最难的是”。你应该说NP完全问题是最难的，因为它们是NP困难问题。 - grom

1

我不确定好运会降临在你身上。政府可能会想要你的头。 - Millie Smith

9

根据我的了解，简单的计算问题（例如在图中查找两点之间的最短路径）可以很快地计算出来（O（n^k），其中n是输入的大小，k是一个常数（对于图来说，它是顶点或边的数量））。

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

但是，计算机科学术语告诉我们的问题是，我们无法将非确定性图灵机转换为确定性图灵机，但是我们可以将非确定性有限状态自动机（例如正则表达式解析器）转换为确定性有限状态自动机（虽然可以，但机器的运行时间会很长）。也就是说，我们必须尝试每条可能的路径（通常聪明的计算机科学教授可以排除一些路径）。

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

这是一个相当鼓舞人心的问题。

- terminus

1

这并不完全正确 - 你可以将非确定图灵机（NDTM）转换为确定图灵机（DTM），但新的机器运行时间呈指数增长，与原始机器的运行时间成正比（你需要对NDTM的状态转换图进行广度优先搜索）。 - Adam Wright

@AdamWright 的回答有点晚了，但扩展机器的运行时间必须与 NDTM 相同，因为按定义它们是等效的。唯一的区别在于，扩展机器碰巧是 NDTM 在给定深度步骤中“实际运行”的结果。 - wafL

6

关于P=?NP问题的“什么”和“为什么”，我无法添加太多内容，但是就证明而言。一个证明不仅值得额外的学分，而且它可以解决其中的一个千禧难题。最近进行了一项有趣的调查，发表的结果（PDF）对于证明的主题绝对值得一读。

- Rob

5

首先，一些定义：

- 如果你可以在时间少于n^k的情况下计算出解决方案（其中k是某个数字），那么特定问题就在P中。例如，排序可以在n log n的时间内完成，这比n^2小，因此排序是多项式时间。 - 如果存在一个k，那么NP问题就在NP中，使得存在一个大小不超过n^k的解决方案，你可以在不超过n^k的时间内验证它。以图形的3着色为例：给定一个图形，3着色是一个（顶点、颜色）对的列表，其大小为O(n)，你可以在O(m)（或O(n^2)）的时间内验证所有邻居是否具有不同的颜色。因此，只有当存在一个短且易于验证的解决方案时，才能对图进行3着色。 - NP的等价定义是“可由多项式时间内的非确定性图灵机解决的问题”。虽然这告诉你名字的来源，但它并没有给你相同的直观感受，即NP问题的特征。

请注意，P是NP的子集：如果你可以在多项式时间内找到一个解决方案，则存在一个可以在多项式时间内验证的解决方案——只需检查给定的解决方案是否等于你可以找到的解决方案。

为什么问题“P =? NP”很有趣？为了回答这个问题，首先需要看看NP完全问题是什么。简而言之，

- 如果L在P中，并且可以用来解决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完全的，那么布尔公式可满足性问题也是NP完全的。

我们知道图的3着色问题是NP完全的；然而，历史上我们首先展示了布尔电路可满足性的NP完全性，然后将其缩小为3着色问题（而不是反过来）。

- Jonas Kölker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dima · Accepted Answer

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种可能性。