假如P=NP，世界将会怎样？

转载自这里：http://www.matrix67.com/blog/archives/2552

 

    在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。 虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在 首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得 怎样？

 
    已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度； 数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上 失去了意义。
    算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。

    一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的 编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。 在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。

    利用Occam剃刀原理，困扰人类已久的自然语言处理问题将被一举攻破。只要提供足够多的语言文字材料，计算机将很快掌握这门语言，并反过来为语 言学提供新的科学体系。考虑这样一个最优化问题：输入一大批语句样本，它们有的符合语法，有的不符合语法；寻找一个最简单的算法，将这些语句输入这个算法 时，算法能正确得出它是否符合语法。显然，这个问题本身是NP的（当然前提是该算法是多项式的），因此计算机可以在多项式时间内找到能判定语法正误的最简 算法。我们有理由相信，这个算法也就是人类头脑中正在使用的算法，因此它能够适用于所给材料之外的其它语句，并具有自我学习的功能。分词技术、手写识别、 语音朗读、语音识别等难题在一瞬间全部攻破。
    很可能计算机给出的自然语言处理算法完全不同于传统语言学的那一套方法，因此传统语言学本身将受到极大的冲击。字、词、句的概念很可能被重新界定，词类、句式的概念有可能被完全颠覆。

    类似地，所有人工智能问题都将得到解决。我们只需要向计算机提交足够多的情境以及与之对应的正常人反应，计算机就可以找出一种能正确生成出 这些反应的最简算法，并且由我们的Occam剃刀假设，这种算法能够适用于更广的范围，完全模仿人类的行为。在网络上，再没有任何办法能够把计算机和人区 别开来。验证码将变得毫无意义。
    计算机不仅能轻易通过图灵测试，还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来，把这个人和网友们的对话全部递交给计算机，计算机将会很快学会如何模仿这个人。网络的身份鉴定将变得相当困难，很可能不得不借助一些物理方式。

    数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单，一切错误的猜想都将瞬间被推翻。事实上，寻找一个数学证明和 验证一个证明的正确性也变得同样简单，因此一切正确的命题也能够瞬间找到一个最简的证明。困扰人类数个世纪的数学猜想将逐一获解。数学领域内部将掀起一次 革命，数学研究真正成为了一门“提出问题的艺术”而不再是“解决问题的艺术”。数理逻辑等底层研究，以及开创数学新分支并将其形式化，将成为数学研究的主 流方向。
    类似地，一切具有解释性并可以形式化的科学都可以借助计算机寻求现象的最佳解释方案。物理学、化学、经济学、心理学等学科都将会受到不同程度的影响。

    md5算法不再有效，判定一个串的md5是否等于给定值与寻找一个md5等于给定值的串一样轻松。RSA算法也不再有效，寻找一个质因子和 判断整除性也变得一样简单。事实上，发明任何新的密码算法都是徒劳——计算机可以根据一大批明文密文样本推算出生成密文的算法（只要这个算法是多项式 的）。现有的密码学体系彻底崩溃。理论上不具有可预测性的一次一密协议成为唯一安全的密码协议。但人们很快注意到，密码本本身的生成也不能依赖于任何伪随 机数算法，必须完全借助于物理算法。从这个角度来说，纯机器的密码协议将不复存在，任何身份验证手续都必须借助物理手段。互联网可能会变得非常不可靠。