P与NP
,还是 或 ,是最著名的尚未解决的计算机科学问题之一。这是一个悬而未决的问题,也是七个问题之一年奖金问题他的解决方案获得了克莱数学研究所颁发的100万美元奖金。虽然 和 只是整个频谱的两类复杂类在…领域内复杂性理论在美国,计算机计算出的大多数常见问题都属于这两类之一。
问题是,一台计算机在快速检查一个难题的解决方案的有效性时,是否也能自己找到解决方案。从解决方案 , 要么多项式时间,问题可以通过计算机快速解决和验证;和解决方案 , 要么非确定性多项式时间问题,验证起来很快,解决起来却非常耗时 暗示着 能同样快地计算出问题吗 ;可以快速验证的问题也可以快速解决。
正式地说,问题在 可以用一个被称为确定性的抽象计算模型解决吗图灵机,通常采取多项式空间,称为多项式空间, ;可以使用NP中的问题非确定性图灵机,并位于所谓的复杂空间中非确定性多项式空间, .
对这个问题的解决方案的兴趣在于,如果是出现的含义 ;最重的就是这个加密算法,或保护所有非常机密的数据的算法很容易被破解,因为它们的安全性依赖于加密算法的计算复杂性 .如果可以轻松找到对所述加密算法的解决方案,则会出于安全目的加密的许多文件,例如整个现代全球电子商务基础设施或在线托管的政府文件。
P算法
绝大多数的计算机科学理论都是关于提高速度和内存空间采取计算算法因为更快的算法为更多的计算提供了额外的时间,占用的空间甚至可能更少并行计算.计算机需要计算问题的时间被称为其时间复杂度, 要么大O符号,而占用的空间称为其空间复杂度.执行这些算法所花费的时间和空间通常以输入的大小和算法必须操作的元素的数量来衡量。
假设老师试图在课堂上找到最高的学生。老师找到这个学生的唯一方法是看看他们中的每一个,跟踪最高学生的名字。出于这个原因,在一类中找到最高的学生 据说学生花费的时间与 ,学生人数。现在,如果不是所有的学生都在教室里,而是在课间休息,老师一次叫两个学生进来,比较他们的身高,找到获胜者,然后再换一对学生,这种成对的比较会花费一定的时间 ,揭示计算解决方案所需的信息。
现在,假设老师试图记录她的算法占用了多少内存空间。在线性时间算法中,它所花费的时间与 当学生们比前辈们高的时候,她就可以把他们的名字写下来。最坏的情况是,她在写作 的名字。然而,她意识到,因为她不需要记录所有比他们的前辈更高的学生的名字,所以她只记录了最高的学生,删除了她之前写下的学生的名字。这将把她的算法占用的空间减少到内存中的单个槽,或成比例 .
随时间和空间增加的算法多项式输入输入,如 那 ,甚至 ,在那里 被提升到一个权力等级,据说属于" “,对于多项式。
NP算法
非常复杂的算法,与算法不同 这些算法需要计算机花费非常长的时间和空间来解决;随着输入元素数量的增加,时间呈指数增长。这个指数时间被描述为任意数的 力量,如 .
虽然看起来问题的范围在 已经很大了,算法所花费的时间 是一个完全不同的幅度。例如,采用线性时间算法,每个元素需要1秒以解决包含100个元素的问题( ).这个问题需要100秒才能解决。它比需要的算法多项式地快 要跑,要与时间成正比 需要几乎三个小时才能处理100个要素。但是,执行时间与之成比例的算法 需要300的万亿年!随着N的无限增长,这种差异会变得更大[1].
问题归类为 ,代表非确定性多项式时间算法,是采取指数时间解决的问题,但可以在多项式时间中验证解决方案的有效性。人们可以想到问题 就像谜语一样,它们很难解决,但一旦给出答案,似乎就很明显了。
素质分解
其中一个最着名的问题之一 是质因数分解,或寻找质数它们相乘形成更大的数。寻找这些质数通常是非常耗时的工作,因为没有多项式时间算法存在。寻找一个数的质数因子最常见的方法是试错,把这个数分成越来越小的块,直到只剩下质数。
如图所示,已知用于考虑n位数的多项式时间算法。但是,给定一组素数,测试它们是否乘以较大的数字是多项式步骤过程。因此,Prime因分分解在 .
大多数计算机科学旨在减少给定的算法的时间和空间复杂性,因为它们转到无限远。虽然它似乎是算法中的范围 是相当大的,算法在 通常超出了计算机的预期。出于这个原因,区分 和 ,并降低复杂性 一个类似于算法的数字 将拯救计算机,人类执行这些计算,是用于其他计算的大量时间。
重要的一点是 问题通常很容易解决,然而 问题被认为是困难的;然而 问题可能有非常大的常数,这使得现代计算机几乎不可能解决它们。此外,还有一些解决方案 问题(如背包问题),可以合理地快速解决,尽管它的时间复杂性仍然在类 .
此外,作为问题 被定义为可以用非确定性图灵机解决的所有问题,然后注意 是复杂性类的子集吗 ,作为解决机械 也可以用问题来解决问题 .中心问题是 然后,询问相反是真的;是否有问题 能用机器解决的问题在哪里 .
NP-Complete的简化和问题
为了回答这个问题 问题,计算机科学家已经找到了一个子集 这些问题至少和其他问题一样难以解决 问题;这意味着对其中一个问题的回答将解决所有问题 问题。这些问题被称为非完全多项式问题。关于问题的大部分研究, , 处理 问题。
非完全多项式问题有两个基本性质:
1)它是NP。2) NP中的每一个问题都是还原在多项式时间内。
减少是 问题,因为它有助于将解决方案从一个问题概括到整个问题的子集。减少是一种将一个问题转换为另一个问题的算法,其中如果问题A被缩小到问题B,并且已知问题B的解决方案,则该解决方案可以用作有效解决问题的子程序。
减少的例子
鲍勃刚搬进镇,试图找到最近的鞋店。自从他尚未购买电话或互联网连接以来,他决定敲玛丽的门,以便获得一些方向。
在互相介绍和鲍勃说明了他的询问之后,玛丽问鲍勃在进城的路上是否经过加油站。由于鲍勃确实看到了加油站,玛丽告诉鲍勃去加油站,向北走一个街区,在东北角找到一家鞋店。
因为玛丽知道鲍勃很容易进入加油站,玛丽通过跳过进入加油站所需的说明来降低找到鞋店的问题。在类似的情况下,如果存在问题 可以在多项式时间和空间中简化为一个问题 那 作为大部分问题 会在简化过程中完成,这需要多项式时间,然后呢 也会在多项式时间内解决,把问题带进来 组合的总多项式时间。
通过将复杂的问题简化为众所周知的、更简单的问题 说,如果 问题被解决后,可以假设约简问题也可以被解决,具有相似的机制和相似的时间复杂度。因此,如果an的多项式时间解 当问题被发现时,它可以用来解决其他所有问题。
为了节省时间,研究人员首先解决了第一个还原问题,即电路周六,目标是决定是否给出的布尔赋值将输出一个1或一个0,一般用于求解坐问题。后,3 sat问题被简化为SAT,一系列的简化开始分类尽可能多的问题 .这些问题包括图着色定理、航班调度、装箱、蛋白质折叠、拍卖定价、超大规模集成电路设计、将肥皂膜最小化,以及赢得《超级玛丽兄弟》[2].建立NP-Complete问题的列表就像建立一个工具箱,可以帮助缩短解决问题的时间 ,这是计算机科学家和数学家试图回答问题的主要方法 能像解决问题一样快吗 .
的研究现状
2002年,61位数学家和计算机科学家进行了一项民意调查 可能不等于 ,而只有9件否则,因为他们后来告诉记者,主要是为了与流行的情绪相矛盾。[1].Scott Aaronson,一位著名的理论计算机科学家,认为大多数技术都证明了这一点 即,找到任何数万个问题之间的单个链接 而不是成千上万个问题中的任何一个 ,但都无济于事;然而,就像其他成功的科学假说一样 假设通过了几次测试,它没有充分的理由通过它是假的。[2].
这 这个问题对于加深理解计算复杂度是极其重要的。最近,很多RSA.密码学通常用于确保互联网交易的安全,它是基于以下假设发展起来的质因数分解很复杂,在吗 并使用蛮力找到解决方案将多年攻击攻击者。但是,新方法量子计算已被发现,可以在多项式时间内极其有效地编号。
Peter Shor,计算机科学和人工智能实验室的计算组(TOC)的成员在麻省理工学院(TOC)制作的发现,使用了大量的计算机量子比特, 哪个是原子在一个离子陷阱.这些计算机使用激光脉冲对每个原子执行算法,正确地分解大数。该系统的设计是为了让更多的原子和激光可以提高机器的效率,使它们能够解决越来越大的数字[3].量子计算机处于减少问题的前沿 到 科学家们相信,在不久的将来,这种减少将很容易计算出来。
参考文献
- 难以置信,L.解释:P与NP.检索2016年6月,来自http://news.mit.edu/2009/explainer-pnp
- Aaronson,S。P的科学案例不等于O NP.从...获得http://www.scottaaronson.com/blog/?p=1720
- 楚,J.加密方案结束的开头?.检索2016年3月,从http://news.mit.edu/2016/quantum-computer-end-encryption-schemes-0303