1971年Stephen A. Cook和Leonid Levin相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?），也就是说，NP问题（Non-deterministic Polynomial）到底是Polynomial，还是Non-Polynomial。问题就在这个问号上，到底是NP等于P，还是NP不等于P。证明其中之一，便可以拿百万美元大奖。 这个奖还没有人拿到，也就是说，NP问题尚无定论。如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。 P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式（Polynomial）的第一个字母。哪些问题是P类问题呢？我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。

P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是Non-Deterministic的意思（图灵机的概念见理论计算机初步：算法和计算模型）。脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。“P/NP问题”不只是一个抽象的数学难题。它还能够一劳永逸地解决计算机的能力问题，即计算机能够解决哪类问题，不能解决哪类问题。计算机能够“轻易”解决P问题；也就是说，根据问题的复杂性，P问题的解在一个有限和合理的时间段内能够找到。同时，对于NP问题来说，找一个解很困难，验证一个解很容易。要计算出一个解或许要花上几十亿年的时间。但一旦找到这个解，就很容易确定这个解的正确与否。（试想一个拼图游戏：拼凑出正确的图形非常难，但一旦完成拼图，你就能一眼看出来它是不是对的。）

NP问题包含很多模式匹配问题和最优化问题，这些问题都有着很大的实际意义，如确定一个硅芯片上晶体管的最优化序列、开发准确的金融预测模型、或分析细胞内的蛋白质折叠行为。NP问题的例子：零子集和问题、旅行商问题、电话网络的最优几何设计、格子棋的最佳走法。

不是NP问题的例子：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。

从上面的定义知道，NP包含P。P=NP？问题指P是否完全等于NP，即确定型图灵机和非确定图灵机的性能是否一样。 

人们为何要提出P=NP？问题？因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。 

NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P=NP？问题的美妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P=NP？。“P=NP？问题”寻找的答案是P问题是否等于NP问题；也就是说，是否每一个NP问题也是一个P问题。若P=NP，那么每个NP问题就还有一个隐藏于世的解决捷径，计算机将有能力快速找到所有完美的解。但若P ≠ NP，那么就没有什么捷径可走，而计算机的解决问题能力从根本上说将是永远受限的。从实际经验得来的猜想是，P问题不等于NP问题。但在有人给出合理的数学证据之前，这个猜想的正确性还值得商榷。