过去一周以来，程序员和计算机科学家们对于最近有人尝试解决计算机科学最难解的问题之一，即所谓的“P/NP问题”，议论不断。

　　8月6号，位于加州帕洛阿尔托的惠普实验室（HP Labs）的研究专家维奈•迪勒里卡（Vinay Deolalikar）将自己发现的“证据”发布到了互联网上，同时还发给了该领域内的一些专家。专家们丝毫不敢怠慢，随即便在学术博客和维基网站上解析了这份证据的正确性。最初，专家对于这份证据是持尊重和怀疑态度的。而到现在，专家们一致认为，迪勒里卡的论证方法有着根本性的错误。

　　假若这份证据确凿无疑，迪勒里卡将名利双收。位于马萨诸塞州坎布里奇的克莱数学研究所（The Clay Mathematics Institute）已经将“P/NP问题”收录入“千禧年”难题，并对任何给出可信证据的人给予100万美元奖励。

　　然而“P/NP问题”不只是一个抽象的数学难题。它还能够一劳永逸地解决计算机的能力问题，即计算机能够解决哪类问题，不能解决哪类问题。计算机能够“轻易”解决P问题；也就是说，根据问题的复杂性，P问题的解在一个有限和合理的时间段内能够找到。同时，对于NP问题来说，要计算出一个解或许要花上几十亿年的时间。但一旦找到这个解，就很容易确定这个解的正确与否。（试想一个拼图游戏：拼凑出正确的图形非常难，但一旦完成拼图，你就能一眼看出来它是不是对的。）

　　NP问题包含很多模式匹配问题和最优化问题，这些问题都有着很大的实际意义，如确定一个硅芯片上晶体管的最优化序列、开发准确的金融预测模型、或分析细胞内的蛋白质折叠行为。

　　“P/NP问题”寻找的答案是P问题是否等于NP问题；也就是说，是否每一个NP问题也是一个P问题。若P=NP，那么每个NP问题就还有一个隐藏于世的解决捷径，计算机将有能力快速找到所有完美的解。但若P ≠ NP，那么就没有什么捷径可走，而计算机的解决问题能力从根本上说将是永远受限的。从实际经验得来的猜想是，P问题不等于NP问题。但在有人给出合理的数学证据之前，这个猜想的正确性还值得商榷。

　　即使迪勒里卡提出的证据是正确的，问题也依然存在——这样一份证据对相关的计算领域将有何影响？

　　表面上看，人们可能会认为“没什么大的影响”。“证明P ≠ NP，只是确认了绝大多数人根据实际经验已经认定为事实的一个猜想的正确性。” MIT计算机科学和人工智能实验室的复杂性研究专家斯科特•阿伦森（Scott Aaronson）说。

　　例如，我们无法胜任对一个大复合数的因子作分解运算（典型的NP问题），这一理论恰是现代密码学的基础。现今，大到国家安全，小到亚马逊的订单，任何安全问题都离不开现代密码学。“我们不需要一个正式的证据来表明P问题不等于NP问题，尽管我们的密码学一直以来依赖的都只是一种猜想。” 阿伦森说，“程序员们都熟悉这个问题，若能亲眼看到P ≠ NP的证据水落石出，想必也会非常兴奋，但考虑到日复一日的工作，那么如何把NP问题转化成简单的问题加以解决，比起解决P ≠ NP这个世纪数学难题，更重要吧。”

　　由于NP问题十分常见（即使是数字拼图游戏和在Bing.com上查询航空时刻表，要计算起来也很有难度），因此，创新的暂时性解决方案也是屡见不鲜。例如，随机规划法模拟了物理系统中的随机性（如冷却金属或DNA突变），为的是找到“足够好”的解，而不是耗尽时间做无休止的计算。

　　尝试相信P问题不等于NP问题这一猜想能够“帮助我们发展新的心理技术”，从事P /NP问题研究的乔治亚理工大学计算机科学家理查德•利普顿（Richard Lipton）说。“虽然我们研究计算机算法已有几十年的历史，但我们还没有完全理解这些算法的全部功能。”他继续道，“因此，即便有人证明了几乎所有人都早已相信的P≠NP问题，我们也必须从根本上扩展我们对算法的理解，并创造出新的计算机应用，而不仅仅是停留在我们已找到的各种巧妙的暂时的解决方案。”

　　如此，如果前进的脚步还能够不断带给我们有价值的创新的话，为什么行业巨头谷歌、微软，和惠普等（这些公司都拒绝对此文章给予评论）不投入研发队伍来解决这个谜团呢？“证明一项否定理论是极其困难的，并且在很多大公司看来，这个问题可能不会影响到下一个财政季度，甚至未来几年的生意，”利普顿说，“这更是一个长期问题。”

　　当然，我们总是有一个备选项：证明P=NP。但别紧张，放轻松。“虽然坚信P=NP的极少数人还是有不错的理由的，”阿伦森说，“但若P问题真的等于NP问题，我们生活的这个世界则会是另一个模样，而我们很可能早就会发现些蛛丝马迹了。”