P = NP的问题可能是所有计算机科学中最着名的问题.这是什么意思？为什么它如此有趣？
哦,为了额外的功劳,请发表声明的真相或虚假证明.:)
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种可能性.
如果答案可以在多项式时间内计算,则在P(P olynomial时间)中是或否问题.
如果可以在多项式时间内验证是答案,则在NP(N确定性P olynomial时间)中是或否问题.
直觉上,我们可以看到,如果问题在P中,则它在NP中.考虑到P中问题的潜在答案,我们可以通过简单地重新计算答案来验证答案.
不太明显,更难以回答的是,NP中的所有问题是否都在P中.我们可以在多项式时间内验证答案的事实意味着我们可以在多项式时间内计算答案吗？
有许多重要的问题已知是NP完全的(基本上,如果任何这些问题被证明在P中,那么所有 NP问题都被证明在P中).如果P = NP,那么所有这些问题将被证明具有有效的(多项式时间)解.
大多数科学家认为P!= NP.但是,尚未确定P = NP 或P!= NP的证据.如果有人提供任何猜想的证据,他们将赢得100万美元.
为了给出我能想到的最简单的答案:
假设我们遇到一个需要一定数量输入的问题,并且有各种可能的解决方案,这些解决方案可能会或可能不会解决给定输入的问题.拼图杂志中的逻辑谜题就是一个很好的例子:输入是条件("乔治不住在蓝色或温室里"),潜在的解决方案是一系列陈述("乔治生活在黄色房子,种豌豆,并拥有狗").一个着名的例子是旅行商问题:给出一个城市列表,从任何城市到任何其他城市的时间和时间限制,潜在的解决方案将是销售人员访问它们的顺序的城市列表,以及如果旅行时间的总和小于时间限制,它将起作用.
如果我们能够有效地检查潜在的解决方案以确定它是否有效,那么这个问题就出现在NP中.例如,给定销售员按顺序访问的城市列表,我们可以将城市之间每次旅行的时间相加,并轻松查看是否在时间限制之内.如果我们能够有效地找到解决方案(如果存在的话),则问题在于P.
(在这里,有效地具有精确的数学意义.实际上,这意味着大问题并非难以解决.在寻找可能的解决方案时,一种效率低下的方法是列出所有可能的潜在解决方案,或者接近该解决方案的方法.虽然有效的方法需要搜索更有限的集合.)
因此,P = NP问题可以这样表达:如果您能够有效地验证上述问题的解决方案,您能找到有效的解决方案(或证明没有)吗？显而易见的答案是"你为什么能够这样做？",这就是今天的问题所在.没有人能够以某种方式证明这一点,这困扰了许多数学家和计算机科学家.这就是为什么任何可以证明解决方案的人都可以从Claypool基金会获得一百万美元.
我们通常假设P不等于NP,没有找到解决方案的一般方法.如果事实证明P = NP,很多事情都会发生变化.例如,密码学将变得不可能,并且在互联网上具有任何形式的隐私或可验证性.毕竟,我们可以有效地获取加密文本和密钥并生成原始文本,因此如果P = NP,我们可以在不事先知道的情况下有效地找到密钥.密码破解将变得微不足道.另一方面,我们可以有效地解决各类规划问题和资源分配问题.
您可能听说过NP-complete的描述.NP完全问题是NP(当然),并且具有这个有趣的特性:如果它在P中,则每个NP问题都是,因此P = NP.如果您能找到一种有效解决旅行商问题的方法,或者从拼图杂志中找到逻辑难题,您可以有效地解决NP中的任何问题.在某种程度上,NP完全问题是NP问题中最难的问题.
所以,如果你能找到一个有效的通用解决方案技术来解决任何NP完全问题,或者证明不存在这样的问题,那么名誉和财富都属于你.
我谦虚知识的简短摘要:
有一些简单的计算问题(比如找到图中两点之间的最短路径),可以很快地计算出来(O(n ^ k),其中n是输入的大小,k是常数(在图的情况,它是顶点或边的数量)).
其他问题,如找到跨越图中每个顶点的路径或从公钥获取RSA私钥更难(O(e ^ n)).
但是,CS说话的问题在于我们无法将非确定性图灵机"转换"为确定性机器,但我们可以将非确定性有限自动机(如正则表达式解析器)转换为确定性机器人(好吧,你可以,但机器的运行时间将花费很长时间).也就是说,我们必须尝试所有可能的路径(通常聪明的CS教授可以排除一些).
这很有趣,因为没有人对解决方案有任何想法.有人说这是真的,有人说这是假的,但没有达成共识.另一个有趣的事情是,解决方案对公钥/私钥加密(如RSA)有害.您可以像现在生成RSA密钥一样轻松破解它们.
这是一个非常鼓舞人心的问题.
对于问题的P =？NP部分,我可以添加的内容并不多,但是在证明方面.一个证据不仅值得一些额外的功劳,而且它将解决千年问题之一.最近进行了一项有趣的民意调查,发表的结果(PDF)绝对值得一读.
首先,一些定义:
一个具体问题是P中,如果你能在计算时间不到解决n^k一些k,这里n是输入的大小.例如,可以在n log n小于的情况下进行排序n^2,因此排序是多项式时间.
如果存在k最多n^k可以及时验证大小的解决方案,则存在NP中的问题n^k.对图形进行3种着色:给定图形,3种颜色是具有大小的(顶点,颜色)对的列表,O(n)您可以及时O(m)(或O(n^2))验证所有邻居是否具有不同的颜色.因此,只有存在简短且易于验证的解决方案时,图表才可以进行3次着色.
NP的等效定义是"问题可以解决由Ñ在ondeterministic图灵机P olynomial时间".虽然这可以告诉您名称的来源,但它并没有给出与NP问题相同的直观感觉.
请注意,P是NP的子集:如果您可以在多项式时间内找到解,那么可以在多项式时间内验证解决方案 - 只需检查给定的解决方案是否与您可以找到的解决方案相同.
为什么这个问题P =? NP很有意思？要回答这个问题,首先需要了解NP完全问题是什么.简单地说,
如果(1)L在P中,则问题L是NP完全的,并且(2)解决L的算法可以用于解决NP中的任何问题L'; 也就是说,给定L'的实例,当且仅当L'的实例有解决方案时,您才能创建具有解决方案的L实例.从形式上讲,NP中的每个问题L'都可以简化为L.
注意,L的实例必须是多项式时间可计算的,并且具有多项式大小,大小为L'; 这样,在多项式时间内求解NP完全问题就可以得到所有 NP问题的多项式时间解.
这是一个例子:假设我们知道图的3色是一个NP难问题.我们想证明决定布尔公式的可满足性也是一个NP难问题.
对于每个顶点v,有两个布尔变量v_h和v_l,以及require(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完全的; 然而,历史上我们已经知道,首先显示布尔电路可满足性的NP完全性,然后将其降低到3可着色性(而不是相反).
京公网安备 11010802040832号 | 京ICP备19059560号-6 