ACM通信
ACM通信
论P、NP和计算复杂度
八月的第二个星期是令人兴奋的一周。8月6日星期五，维奈·德奥拉利卡尔宣布了一项声称的证据P＃NP．8月7日和8日，slash网点博客发布了这一消息，突然间全世界都开始关注。理查德·利普顿8月15日在blog@CACM上发表的博客在一周内就有大约1万名读者浏览。数以百计的计算机科学家和数学家，在一个基于网络的大规模协作中，仔细分析了这个证明，试图验证它的有效性。到那时纽约时报8月16日发表了一篇关于这个话题的文章，发现了主要的差距，人们的兴奋开始消退。的Pvs。NP“问题”经受住了另一次挑战，依然敞开大门。
在那激动人心的一周期间和之后，许多人请我解释这个问题，以及为什么它对计算机科学如此重要。“如果每个人都这么认为的话P是不同的NP有人问我，“为什么证明这种说法如此重要?”答案当然是相信和知道是不一样的。传统的“智慧”可能是错误的。虽然我们的直觉确实告诉我们，寻找解决方案应该比检查解决方案更难，这就是Pvs。NP问题在于，直觉可能是通向真理的糟糕向导。举个例子:现代物理学。
而Pvs。NP进退两难是计算机科学中的一个中心问题，我们必须记住，对这个问题的解决可能具有有限的实际影响。可想而知，P＝NP，但多项式时间算法的证明是完全不切实际的，由于多项式的程度非常大或乘常数非常大;毕竟,(10n）1000是一个多项式!同样，可想而知PNP,但NP问题可以用运行时间为的算法来解决nLog Log Log n这个边界不是多项式，但表现得非常好。
我认为，更重要的是，计算复杂性理论对现实世界中算法行为的解释有限。以布尔满足性问题(SAT)为例，这是一个规范的问题NP推进问题。当我还是一个研究生的时候，SAT是一个“可怕的”问题，连10英尺高的杆子都不敢碰。加里和约翰逊的经典教科书显示，有一长串程序员都没能解决问题NP推进问题。你猜怎么着?这些程序员一直很忙!2009年8月号通信包含一篇文章(第76页)，他们描述了SAT从理论困难到实际成功的历程。今天的SAT求解器在工业上得到了广泛的应用，它通常用一个以上的SAT实例来求解SAT实例几百万变量。一个可怕的NP-完整的问题就这么简单?这是怎么回事?
答案是人们必须仔细阅读复杂性理论的声明。经典NP-完整性理论是关于最坏的的复杂性。
事实上，SAT在最坏的情况下似乎也很难。有些SAT实例包含几百个变量，任何现有的SAT求解器都无法解决这些变量。“那又怎样?”从业者耸耸肩说，“这些都是人为的问题。”在某种程度上，工业SAT实例非常适用于当前的SAT解决技术，但我们没有好的理论来解释这一现象。复杂性理论中有一个分支是研究平均案例复杂性的，但这项研究似乎对实际的SAT解题也没有什么帮助。如何设计好的算法是计算机科学中最基本的问题之一，但复杂性理论仅为算法设计提供了非常有限的指导。
一位老cliché问理论和实践的区别是什么，他回答说:“在理论上，它们没有那么大的区别，但在实践中，它们有很大的区别。”这似乎适用于SAT的理论和实践以及类似的问题。我在这里不是要批评复杂性理论。这是一个美丽的理论，在过去的50年里产生了深刻的见解，也提出了根本性的、诱人的问题，比如Pvs。NP问题。但理论的一个重要作用是照亮实践，在这方面我们有很大的差距。我相信，我们需要一个更丰富、更广泛的复杂性理论，一个既能解释SAT这类问题的难易之处的理论。
摩西·y瓦迪主编
©2010 acm 0001-0782/10/1100 $10.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。
评论
CACM管理员
以下这封信发表在2011年2月出版的《致编辑的信》(//www.eqigeno.com/magazines/2011/2/104382)上。
——CACM管理员
关于Moshe Y. Vardi在他的编辑信“On P, NP, and computational complexity”(2010年11月)中关于计算复杂性的观点，我想补充一点，计算复杂性的目标是探索高效计算的潜力和限制。虽然P vs. NP是这一方向的中心枢纽，但计算复杂性并不仅仅局限于此;然而，我的评论仅限于P与NP。
P vs. NP指的是找到计算问题的解决方案的相对难度，而不是检查这些问题的解决方案的正确性。常识表明，找到解比检查其正确性更困难，人们普遍认为P不同于NP。瓦尔迪主张研究P和NP，他说知道和相信是不同的，并警告相信有时是错误的。
证明一个核心结果的能力与对一个领域核心的主要问题获得更深入的理解有关。因此，证明P不同于NP最有可能导致对高效计算的更好理解，而这种理论理解必然会对计算机实践产生重大影响。此外，甚至在这一过程中发展出来的想法，试图解决P与NP的问题，影响了计算机实践;比如，SAT解题题。
这并不反驳理论与实践之间存在差距的说法;理论不应该取代实践，而应该为实践提供信息。我们不应该低估好的建议或好的理论的价值;任何人都不应高估它。现实生活中的问题是在实践中解决的，但好的实践会从好的理论中受益匪浅。
人们还应该意识到，P vs. NP问题的具体表述(就多项式运行时间而言)只是一个更抽象问题的最简单表述。对最坏情况复杂性的关注也是如此。在任何一种情况下，当前的公式都应该被视为第一近似，在继续向前发展之前，研究和理解它是有意义的。
不幸的是，对于大多数关于高效计算的自然问题，我们缺乏好的理论答案，不是因为我们问了错误的问题，而是因为答案太难了。
尽管与问题相比，我们的理解有限，但就几十年前的知识而言，我们已经取得了重大进步。此外，这一理论进展影响了计算机实践(如密码学)。考虑到目前对高效计算的理解，大多数计算机科学实际上都在尽力开发最好的计算工具，而不是等待一些雄心勃勃但遥远的项目取得充分进展，这是有道理的。理论计算机科学(TCS)有助于应对当今的实际挑战也是有道理的。但是，对于TCS复杂性理论的一个特殊方面来说，致力于理解高效计算的可能性和局限性是至关重要的。
欧迪Goldreich
以色列Rehovot
显示1评论