P对NP问题是Steve Cook于1971年提出。“P/NP问题”，这里的P指多项式时间（Polynomial），一个複杂问题如果能在多项式时间内解决，那幺它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个複杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。比NP问题更难的则是NP完全和NP-hard，如围棋便是一个NP-hard问题。2010年8月7日，来自惠普实验室的科学家Vinay Deolalikar声称已经解决了“P/NP问题” ，并公开了证明档案。

如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的複杂性是O(nlgn)，排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的複杂性是指在所有的解决该问题的算法中最好算法的複杂性。问题的複杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。

为了研究问题的複杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者 no的问题。任何一般的最最佳化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。。。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的複杂度是该问题的一个实例的规模n的多项式函式，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有複杂度为多项式时间的问题的集合。有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿迴路问题，我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿迴路问题，给一个任意的迴路，我们很容易判断他是否是哈米尔顿迴路（只要看是不是所有的顶点都在迴路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，现在的问题是，P是否等于NP?这个问题至今还未解决。这就是P对NP问题。

“P类”、“NP类”、“更複杂的类”，是确定型Turing机DTM中的不同複杂性分类。这些分类是由不同问题的性质决定的，还是我们目前没有找到好的DTM解决方法形成的？这就是“P对NP”问题上。它的基本意思是

（1）P=NP我们最终能够找到一些计算方法，使得NDTM能够快速解决的问题，在DTM上也能够快速解决。快速的意思是“使用不超过输入字元串的多项式时间”。

（2）P≠NPNP只能用NDTM快速解决，而不能用DTM快速解决。

假如P≠NP，关于NP类内部的结构，可以再分成3个区域P、NPC和NPI。

NPC和是NP里“最难的”问题，因为任何NP中的问题可以在多项式时间内变换成为任何特定NPC（NP-完全问题，NP-completeness）的一个特例。这就是说，如果找到一个NPC问题的快速解决方法，则所有的NP问题都可以快速解决了。NPI是NP中既不是P又不是NPC的问题类，如果P≠NP。

例如，密码学中的“素数分解”（大数分解和素性检测），就是一个NPC问题。假如P=NP，密码学的工作者必须改造的工作，实在是太多了！如果P=NP，则现有的大量密文都是容易解密的。

注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，P属于NP，所以也是 NP问题，你能说他很难解幺？刚才说了，现在还不知道是否有P=NP或者P<>NP，后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。 NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿迴路问题就是一个NPC问题。NPC问题的历史并不久，cook在 1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，也不是不可能）。类似哈米尔顿迴路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。

要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行推销员问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。 所以若旅行商问题被证明为在P内，则P = NP！旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

关于“P对NP”问题对密码学的影响，请看着名计算机科学家Stephen Cook（第一个NPC的提出者，1971年提出）2003年在“The importance of the P versus NP question”中的原始论述。Cook的基本看法是

如果证明了P=NP，那幺依据计算複杂性的密码术就是没有用途的。Internet（包含财政情报）的安全性是建立在这些假设上大素数的分解、DES (the Data Encryption Standard)的解密，不能用数字计算机快速地解决。相反，量子密码术不受P=NP的影响，可能解决Internet的安全性问题。

如果证明了P≠NP，那幺大素数的分解还是不是NPC的？证明RSA、DES等密码术的安全性比证明P1NP还困难。

不仅依据离散量运算的密码学受到“P对NP”问题的影响，而且依据连续量运算的密码学也受到实数环上的“P对NP”问题的影响。但人脑具有“潜意识”等非数学智慧型，如具有形象思维、动作思维、灵感直觉等，安全的密码学总是存在的。正常人右脑的非数学智慧型明显高于左脑的数学智慧型（Roger W. Sperry获得1981年诺贝尔奖The Nobel Prize in Physiology or Medicine的工作），未来更安全密码学的发展是没有止境的！

如果P=NP，那幺每个答案很容易得到验证的问题也同样可以轻鬆求解。这将对计算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。

而现在，美国惠普实验室的数学家维奈·迪奥拉里卡围绕一个众所周知的NP问题进行论证，给出了P≠NP的答案。这就是布尔可满足性问题(Boolean Satisfiability Problem)，即询问一组逻辑陈述是否能成立或者互相矛盾。迪奥拉里卡声称，他已经证明，任何程式都无法迅速解答这个问题，，它不是一个P问题。

如果迪奥拉里卡的答案成立，说明P问题和NP问题是不同的两类问题，这也意味着计算机处理问题的能力有限，很多任务的複杂性从根本上来说也许是无法简化的。

对于有些NP问题，包括因数分解，P≠NP的结果并没有明确表示它们是不能被快速解答的；但对于其子集NP完全问题，却注定了其无法很快得到解决。其中一个着名的例子就是旅行商问题(Travelling Salesman Problem)，即寻找从一个城市到另一个城市的最短路线，答案非常容易验证，不过，如果P≠NP，就没有电脑程式可以迅速给出这个答案。

迪奥拉里卡的论文草稿已经得到了複杂性理论家的认可，但随后公布的论文终稿还将接受严格的审查。