P versus NP：多项式对非确定多项式

多项式对非确定多项式（P对NP，P versus NP，polynomial versus nondeterministic polynomial）是指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，那么不管数字密码有多复杂，它都将可能破解，因此也就是说所有的数字加密方法将都是没有价值的。

最近更新时间：2008-06-17 EN