什么是“P = NP?”,为什么这么着名?

P = NP是否可能是计算机科学领域最着名的问题。 这是什么意思? 为什么这么有趣?

哦,为了额外的功劳,请张贴陈述真相或虚假的证据。 🙂

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

定义:

  • 多项式时间意味着algorithm的复杂度为O(n ^ k),其中n是数据的大小(例如,要sorting的列表中的元素的数量),并且k是常数。

  • 作为数据项数量的函数, 复杂性是根据所需操作的数量来衡量的。

  • 作为特定任务的基本操作, 操作是有道理的。 对于sorting的基本操作是一个比较。 对于matrix乘法,基本操作是两个数字的乘法。

现在的问题是,确定性与非确定性的含义是什么? 有一个抽象的计算模型,一个名为图灵机(TM)的虚拟计算机。 这台机器的状态数量是有限的,还有一个无限的磁带,它具有离散的单元,其中可以写入和读取一组有限的符号。 TM在任何时候都处于其状态之一,正在看磁带上的特定单元。 根据从单元格中读取的内容,它可以在该单元格中写入新的符号,将磁带向前或向后移动一个单元格,并进入不同的状态。 这被称为状态转换。 令人惊讶的是,通过仔细地构造状态和转换,你可以devise一个TM,它相当于任何可以写入的计算机程序。 这就是为什么它被用作certificate计算机能做什么和不能做什么的理论模型。

在这里有两种关注我们的TM:确定性的和非确定性的。 一个确定性的TM只有从每个符号的每个符号的一个转换,它从磁带上读取。 一个非确定性的TM可能有几个这样的转换,即它能够同时检查几种可能性。 这就像产生多个线程一样。 不同的是,一个非确定性的TM可以产生尽可能多的这样的“线程”,而在真实的计算机上,一次只能执行特定数量的线程(等于CPU的数量)。 实际上,计算机基本上是具有有限磁带的确定性TM。 另一方面,除了可能用量子计算机之外,一个非确定性的TM不能被物理地实现。

已经certificate,任何可以通过非确定性TM解决的问题都可以通过确定性TM来解决。 但是,目前还不清楚需要多less时间。 语句P = NP意味着如果一个问题在一个非确定性的TM上需要多项式时间,那么可以build立一个确定性的TM,它也将在多项式时间内解决相同的问题。 到目前为止,还没有人能够certificate它是可以做到的,但是没有人能够certificate它不能做到。

NP完全问题意味着一个NP问题X,使得NP问题Y可以通过多项式约化减less到X. 这意味着如果有人提出了一个NP完全问题的多项式时间解,那么也将给出任何NP问题的多项式时间解。 这样就certificateP = NP。 相反,如果有人要certificateP!= NP,那么我们可以确定在传统的计算机上没有办法在多项式时间内解决NP问题。

一个NP完全问题的例子是find一个真值分配的问题,这个分配会使一个包含n个variables的布尔expression式成立。
目前在实践中,任何在非确定性TM上花费多项式时间的问题只能在确定性TM或常规计算机上以指数时间完成。
例如,解决真值分配问题的唯一方法是尝试2 ^ n个可能性。

  1. 如果答案可以在多项式时间内计算,则PP olynomial time)中的是或否问题。
  2. 如果可以在多项式时间内validation是的答案,那么在NPN on-deterministic P olynomial时间)中,是或否的问题是。

直觉上,我们可以看到,如果问题出现在P中 ,那么它就是NP 。 给出P中潜在的问题答案,我们可以通过重新计算答案来validation答案。

不太明显,更难回答的是NP中的所有问题是否都在P中 。 我们可以在多项式时间内validation答案的事实是否意味着我们可以在多项式时间内计算答案?

有许多重要的问题已知是NP完全的 (基本上,如果这些问题被certificate在P中 ,那么所有的 NP问题都被certificate在P中 )。 如果P = NP ,那么所有这些问题将被certificate有一个有效的(多项式时间)解决scheme。

大多数科学家认为P != NP 。 但是,对于P = NPP != NP还没有证据。 如果有人提供了猜测的证据, 他们将赢得100万美元 。

为了给出最简单的答案,我可以想到:

假设我们有一个需要一定数量的input的问题,并且有各种可能的解决scheme,这些解决scheme可能或不可能解决给定input的问题。 一个益智杂志中的逻辑谜题将是一个很好的例子:input是条件(“乔治不住在蓝色或绿色的房子里”),潜在的解决scheme是一个陈述清单(“乔治住在黄色房子,生长豌豆,并拥有狗“)。 一个着名的例子是旅行推销员的问题:给出一个城市的列表,以及从任何一个城市到其他任何城市的时间,以及时间限制,一个潜在的解决scheme将是一个推销员访问他们的顺序的城市列表,如果旅行时间的总和小于时间限制,那么它就可以工作。

如果我们能够有效地检查一个潜在的解决scheme,看看它是否有效,那么这个问题就在NP中。 例如,给出推销员按顺序访问的城市列表,我们可以将城市之间的每次旅行的时间加起来,并且容易地看到是否在时间限制之内。 如果我们能够有效地find解决scheme,那么问题出在P上。

(这里有效,这里有一个精确的math意义,实际上这意味着大问题不是不合理地难以解决的,当寻找一个可能的解决scheme时,一个低效的方法是列出所有可能的解决scheme, ,而一个有效的方法将需要search一个更有限的集合。)

因此,P = NP问题可以用这种方式expression:如果能够有效地validation上述types问题的解决scheme,您是否能够有效地find解决scheme(或者certificate没有解决scheme)? 显而易见的答案是“为什么你应该能够?”,而这正是今天的问题。 没有人能够以这种或那种方式来certificate这一点,而这又困扰了很多math家和计算机科学家。 这就是为什么任何能certificate解决scheme的人都能从Claypool基金会获得一百万美元的收益。

我们通常假设P不等于NP,没有find解决scheme的一般方法。 如果结果是P = NP,很多事情都会改变。 例如,密码学将变得不可能,并且在互联网上具有任何types的隐私或可validation性。 毕竟,我们可以有效地把encryption的文本和密钥生成原始文本,所以如果P = NP,我们可以在事先不知道的情况下有效地find密钥。 密码破解将变得微不足道。 另一方面,我们可以有效地解决一整套的计划问题和资源分配问题。

您可能听说过NP-complete。 一个NP完全问题是一个NP(当然),具有这个有趣的性质:如果它在P中,每个NP问题都是,那么P = NP。 如果你能find一种方法来有效地解决旅行推销员的问题,或从谜题的逻辑谜题,你可以有效地解决NP中的任何事情。 NP完全问题在某种程度上是最困难的NP问题。

所以,如果你能为任何NP完全问题find一个有效的通用解决scheme,或者certificate没有这样的解决方法,那么名利就是你的。

我卑微的知识简短总结:

有一些简单的计算问题(如find图中两点之间的最短path),可以很快计算(O(n ^ k),其中n是input的大小,k是一个常数的graphics,这是顶点或边的数量))。

其他问题,比如find一个跨越图中每个顶点的path,或者从公钥中获取RSA私钥更困难(O(e ^ n))。

但CS说,问题是我们不能将非确定性的图灵机“转换”为确定性的图灵机,然而,我们可以将非确定性的finine自动机(如正则expression式parsing器)转换为确定性的可以,但机器的运行时间会很长)。 也就是说,我们必须尝试一切可能的path(通常聪明的CS教授可以排除几个)。

这是互相干扰的,因为没有人对溶剂有任何的想法。 有人说这是真的,有人说这是假的,但没有共识。 另一个值得注意的事情是,对于公钥/私钥encryption(比如RSA)来说,这种欺骗是有害的。 您可以像现在生成一个RSA密钥一样轻松地将其分解。

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

我可以补充什么,为什么问题的P =?NP部分,但是关于certificate。 不仅是一个certificate值得额外的信贷,但它将解决千年问题之一 。 最近进行了一个有趣的调查, 发表的结果(PDF)对于certificate的主题是绝对值得的。

首先是一些定义:

  • 一个特定的问题是在P中,如果你可以计算一个小于n^k对于某个k ,其中n是input的大小。 例如,sorting可以在小于n^2 n log n完成,因此sorting是多项式时间。

  • 如果存在一个k ,那么存在一个问题在NP中,使得存在至多n^k的大小的解决scheme,其可以在至多n^k时间内进行validation。 以图的三着色:给定一个图,三着色是大小为O(n)的(顶点,颜色)对的列表,并且可以在时间O(m) (或O(n^2) )所有邻居是否有不同的颜色。 所以一个图只有在有一个简短且易于validation的解决scheme时才是可着色的。

NP的等价定义是“在多项式时间内由N个不确定性图灵机可解的问题”。 虽然这告诉你名字来自哪里,但它不会给你NP NP问题的直觉。

注意P是NP的一个子集:如果你可以在多项式时间内find解,那么就有一个解决scheme可以在多项式时间内进行validation – 只要检查给定的解与你能find的解相等。

为什么问题P =? NP P =? NP有趣? 要回答这个问题,首先需要看看NP完全问题是什么。 简单地说,

  • 如果(1)L在P中,且(2)求解L的algorithm可用于解决NP中的任何问题L',则问题L是NP-完全的; 也就是说,给定一个L'的实例,当且仅当L'的实例有一个解决scheme时,才可以创build一个具有解决scheme的L的实例。 从forms上讲,NP中的每个问题L'都可以归结为L

注意,L的实例必须是多项式时间可计算的,并且具有L'大小的多项式大小; 这样,在多项式时间内求解NP完全问题给了我们所有 NP问题的多项式时间解。

下面是一个例子:假设我们知道图的3染色是NP难题。 我们想certificate决定布尔公式的可满足性也是NP难题。

对于每个顶点v,有两个布尔variablesv_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 ...)列举所有的平等configuration,并规定他们都不是这种情况。

AND将所有这些约束条件一起给出具有多项式大小( O(n+m) )的布尔公式。 您可以检查是否需要计算多项式时间:您正在为每个顶点和每个边执行简单的O(1)填充。

如果你能解决我所做的布尔公式,那么你也可以解决图着色问题:对于每一对variablesv_h和v_l,让v的颜色与那些variables的值匹配。 通过构build公式,邻居不会有相同的颜色。

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

我们知道图的3染色是NP完全的; 然而,历史上我们已经知道,首先显示布尔电路可满足性的NP完全性,然后将其降低到3色可用性(而不是其他方式)。