p vs np(p versus np)

P对NP（多项式对非确定多项式）是指1971年Leonid Levin和Stephen Cook提出的一个关于容易被解答的问题（p型）以及相反的难以解答的问题（NP型）的数学理论问题。任何P型问题都能够按照“多项式时代”解答（一个多项式包含许多项，每个项又包括了一个变量或者是乘以一个系数的变量的幂。）一个P型的问题是位的数字的多项式，它用以描述问题的情况，一个P型问题的具体例子就如在map（link工具生成的一种文本文件，其中包含有被连接的程序的某些信息，例如程序中的组信息和公共符号信息等。）上找到从点A到点B的路径。一个NP型的问题需要花费大量的时间去解决，所花的时间甚至比它表述一个问题花的时间要多得多，其具体的实例如破解一个128位的数字密码。P对NP型问题在通讯中是非常重要的，因为它可以最终决定数字加密方法的有效性（或者是无效性）。　NP问题否认了在解决方法上的任何强力途径，因为找到正确的解决办法将需要亿万年或者更长的时间，即使世界上所有的超型计算机都用于完成这个任务。一些数学家们认为可以通过提高计算机同时尝试一个问题的每种可能性能力而克服这个障碍。这个假设称之为P等于NP。而其他人则认为如此的计算机没有可能发展（因为P并不等于NP）。如果它变成了P等于NP，那么不管数字密码有多复杂，它都将可能破解，因此也就是说所有的数字加密方法将都是没有价值的。

很显然的是Ｐ类都属于ＮＰ类（P ⊆ NP），这样问题就变成：是否某些NP类问题（比如旅行推销员问题）不存在多项式时间过程算法? 问题难在如何证明这一点？如何从逻辑上排除旅行推销员问题存在多项式时间过程算法的可能性？这跟黎曼假设的严格数学证明要排除临界线外有复零点的可能性一样困难。

很多研究复杂性理论的专家都认为 Ｐ≠ＮＰ，MIT的Scott Aaronson从哲学角度发表了他的看法：“如果P = NP，那么我们就会处于一个截然不同的世界中，创造性飞跃将失去其难能可贵的价值，解决一个问题和认识到问题有解没什么分别。任何一个能欣赏交响乐的人都能成为莫扎特，任何一个懂得数学证明的人都能成为高斯...”。