千年之谜P与PN

18数宁静致远 · 发表于 2018-7-12 11:54:59

本帖最后由 16杰杰于 2018-7-13 20:34 编辑

千年之谜（三）P与NP问题：改变世界格局的神秘钥匙

黄逸文中国数学会 1周前

在所有的千年之谜中，有一个极其特殊的问题。它的诞生和计算机的出现息息相关。虽然距离它的提出，已经度过了47年的悠悠岁月，却仍然是最年轻的千年难题。

令人惊异的是，其它所有千年问题的解决都强烈依赖于高度专业的数学训练，唯有开启它的钥匙却可能掌握在一个“无名的业余爱好者”手中。无需拥有高深的数学知识，一个人就可能在突发奇想间找到破译它的密码。要打开这座尘封半个世纪的宝藏，人们需要的，仅仅是天马行空的想象力。这就是著名的P与NP问题。

图1 P vs. NP（图片来源：hight3ch.com）

计算机之于信息时代

进入信息时代以来，人们的生活愈发离不开计算机的辅助。无论是个人的学习、工作、娱乐，甚至衣食住行，又或是群体的商业往来、竞技比赛、交通运输、信息通讯、工业制造等等都因为计算机的参与而被纳入到信息时代的轨道之中。计算机因为其强大的效率和生产力，已经渗透到当代人们生活的每一个角落。

不仅如此，最尖端的科学研究、国防军工、航空航天以及人工智能、大数据分析都已经深深地依赖于计算机的性能。历史上从来没有一个时代，人们如此地仰仗于一个工具来塑造自己的生活。

计算机对人们生活的影响主要体现在硬件和软件之上。一方面，昔日“失之毫厘、谬以千里”的古训在今天已经成为现实。基于硬件的半导体工艺水平伴随着摩尔定律每隔18个月就会翻倍。这意味着即使计算机的性能落后2年，整体的性能就可能落后3倍。这在科技竞争和国防事业中会造成不可承受的天壤之别。也因此，每一个有志立足于世界民族之林、在世界尖端科技的潮流中勇争一席之地的国家，都将计算机的发展视为最重要的国之利器。

图2 现代人的工作完全离不开计算机（图片来源：web3canvas.com）

另一方面，在硬件技术远远落后的情况下，后发者想取得先发优势，唯有充分利用已有计算机的计算能力，将软件的效能发挥到极致。P与NP问题也就诞生于人们追求计算机解决问题的效率之中。这一切，又起源于希尔伯特在1900年提出的第十问题。

希尔伯特的问题是设想是否存在一系列的机械步骤，使之能判定一般的丢番图方程是否有解。在那个年代，人们对机械步骤的定义尚不明确，但这意外地激发了英国数学家图灵（Turing）的兴趣。图灵机的概念就在他研究希尔伯特第十问题的过程中横空出世。这为后世计算机的理论奠定了牢不可破的基础。

图3 图灵（1912-1954）和图灵机（图片来源：ilovemanchester.com）

1931年，奥地利数学家哥德尔（Godel）天才般地证明了“不完备定理”，颠覆了希尔伯特希望通过公理化体系来完成一切数学证明的愿望。在文章中，哥德尔展示了如何将可证明性的问题转化为与之等价的某种可计算性的问题，从而建立了“可计算函数”概念的形式理论。“可计算性”概念的澄清和图灵机的构想，终于帮助人们打开了通往现代计算机的大门。

P=NP?

随着计算机的广泛应用，它能处理的问题也愈来愈复杂，随之而来对计算机的性能和软件的效率提出了极高的要求。因此，一门关于计算机解决问题效率的复杂性理论应运而生。这其中的首要问题就是要找出一种方法来度量在一台计算机上执行一项特定任务需要多长的时间。很明显，一个问题具有的数据越多，花费在计算机上的时间就越长。人们迫切希望知道，计算机解决问题的时间与数据量的增长额度的关系。人们把这种关系称作这个过程的“时间复杂性函数”。而P问题，就是多项式问题，指代的是时间过程以多项式表达式为时间复杂性函数的过程。

幸运的是，P问题是计算机能够有效处理的问题，人们可以为解决一个问题而等待多项式复杂度的时间。比如计算机做乘法计算就是多项式时间复杂度的典型例子。不幸的是，还存在着一类问题，它消耗的计算机时间以指数函数为复杂度。每增加一个计算量，就可以导致计算时间翻倍，比如围棋的博弈。这远远超过了人们能够等待的生命时间。

多项式时间过程与指数时间过程之间存在着巨大的鸿沟，人们逐渐意识到需要寻找一种中间尺度的复杂性过程。于是，第三种模型：NP问题也呼之欲出。NP问题指代一种非确定性多项式的时间过程。一般而言，计算机都是确定性的过程——它们按照事先规定好的规则以一种完全确定的方式工作。非确定性则代表这样一种可能，计算机在执行某个任务时，可以随机地猜测下一步的行动，如果这个选择的运气足够好，使得它每次都能做出最佳的选择，那么它就能在多项式时间内解决该问题。

图4 P=NP?（图片来源：维基百科）

NP问题介于多项式问题和指数时间问题之间，但是它建立在一个完全不现实的想法基础之上，即有一种计算机总是能在每一步做出最佳的随机选择，然而它却在随后的生产实践中发挥着重大的作用。事实上，在工业和管理中出现的大多数指数时间问题都是NP型的。

因此，NP分类在20世纪60年代被提出之后，人们就希望P与NP类问题并不是同一类问题。然而，谁也无法证实这一猜测。此时，来自美国的库克（Cook）于1971年证明了一个匪夷所思的结论。在那篇著名的论文中，库克断言，存在一个特殊的NP问题，它具有一种奇特的性质，如果这个特殊的问题能用多项式时间过程解决，那么其他任何的NP问题也能！这个性质被库克命名为NP完全性。随后，很多重大的工业和商业问题都被证明是NP完全问题，比如邮差送信、旅行路线规划问题等等。然而，NP完全问题因为其诡异的性质而被认为最不可能是P类的问题。不久，库克和乐文（Levin）各自独立提出了如今的第三个千年之谜，NP完全问题是否可能由计算机在多项式时间内解决，即P与NP问题是否是同一类问题？

图4 库克（1939-）和乐文（1948-）图片来源：claymath.org

结语

P与NP的等价性及其证明，将彻底颠覆人们对所有可计算问题的认识，其影响力将冲击到现代世界的每一个角落。如果P与NP问题最终被证明是等价的，那么基于数字密码的所有加密系统都将是不安全的，它都能在多项式时间内被计算机破解，从而破坏人们赖以生存的信息安全网络。这会对基于互联网的安全产生极其严重的后果，对世界经济强烈依赖于电子通信安全的基础给予致命性的打击。因此，不管P与NP问题最终的结果如何，它的解决必将带来世界经济和安全格局的焕然一新。
黄逸文(中国科学院数学与系统研究院)