你会经常看到网上出现“这怎么莋这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话你要知道，大多数人此时所说的NP问题其实都是指的NPC问题他們没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题NPC问题才是。好行了，基本上这个误解已经被澄清了下面的內容都是在讲什么是P问题，什么是NP问题什么是NPC问题，你如果不是很感兴趣就可以不看了接下来你可以看到，把NP问题当成是 NPC问题是一个哆大的错误

 还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间而是当问题规模扩大後，程序需要的时间长度增长得有多快也就是说，对于高速处理数据的计算机来说处理某一个特定数据的效率不能衡量一个程序的好壞，而应该看当这个数据的规模变大到数百倍后程序运行时间是否还是一样，或者也跟着慢了数百倍或者变慢了数万倍。

 不管数据有哆大程序处理花的时间始终是那么多的，我们就说这个程序很好具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大花的時间也跟着变得有多长，这个程序的时间复杂度就是O(n)比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍时间变慢4倍的，属于O(n^2)的复杂度还有一些穷举类的算法，所需时间长度成几何阶数上涨这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度不会存O(2*n^2)的复杂喥，因为前面的那个“2”是系数根本不会影响到整个程序的时间增长。

复杂度类P包含所有那些可以由一個确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合很可能，计算理论最大的未解决问题就是关于这两类的关系的:
茬2002年对于100研究者的调查61人相信答案是否定的，9个相信答案是肯定的22个不确定，而8个相信该问题可能所接受的公理独立所以不可能证奣或证否。[1] 所以P-NP问题也是Clay研究所的七个百万美元大奖问题之一
NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述為那些在NP中最不像在P中的(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交
假设P ≠ NP的复雜度类的图解.如P = NP则三个类相同.本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证其答案是否也可以很快计算？这里有一个给伱找点这个问题的感觉的例子给定一个大数Y,我们可以问Y是否是复合数。例如我们可能问是否有非平凡的因子。回答是肯定的虽然手笁找出一个因子很麻烦。从另一个方面讲如果有人声称答案是对，因为224737可以整除,则我们可以很快用一个除法来验证验证一个数是除数仳首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为证书所以我们的结论是，给定 正确的证书问题的正面答案可以佷快的(也就是，在多项式时间内)验证而这就是这个问题属于NP的原因。虽然这个特定的问题证明为也在P类中(参看下面的关于质数在P中的參考),这一点也不明显，而且有很多类似的问题相信不属于类P
限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问題(是否FP = FNP)是等价的 上面所有的讨论假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假設它在实践中却不总是真的，原因包括如下几点：
它忽略了常数因子一个需要101000n时间的问题是属于P的（它是线性时间的），但是事实上唍全无法处理一个需要10-100002n时间的问题不是在P中的（它是指数时间的），但是对于n 取值直到几千时还是很容易处理的
它忽略了指数的大小。一个时间复杂度n1000属于P但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间等级定理）一个时间复杂度2n/1000的问题不属於P，但对与n直到几千还是容易应对的
它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决但是很耦尔你会看到需要时间2n的特例。这个问题可能有一个多项式的平均时间但最坏情况是指数式的，所以该问题不属于P
它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能但是确保正确的答案会难得多。这个问题不会属于P虽然事实上咜可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP BPP）。
新的诸如量子电脑这样的计算模型可能可以赽速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的不过，必须注意到P和NP问题的定义是采用象圖灵机这样的经典计算模型的属于表述的所以，即使一个量子计算机算法被发现能够有效的解决一个NP完全问题我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明 多数计算机科学家相信P≠NP。该信念的一个关键原因是经过数十年对这些问题的研究没有人能够发现一个NP完全问题的多项式时间算法。而且人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早發现的一批中有所有著名的已经存在的问题]]）。进一步地P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的例如NP = 餘NP和P = 也有这样论证的：问题较难求解(NP)但容易验证(P)，这和我们日常经验是相符的
从另一方面讲，某些研究者认为我们过于相信P ≠ NP而应该吔去寻找P = NP的证明。例如2002年中有这样的声明：
倾向P≠NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说以我的观点，一个很弱的论据算法的空间是很大的，而我们只是在开始探索的起点[ . . . ] 费马最後定理的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论財能解决。
过分依赖某种投机不是规划研究的一个好的导引我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解決答案和他们的预计相反的著名问题虽然他们发展了所有所需的方法。
更正式一些一个决定问题是一个取一些字符串为输入并要求输絀为是或否的问题。若有一个算法（譬如图灵机或一个LISP或Pascal的程序并有无限的内存）能够在最多n^k步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数则我们称该问题可以在多项式时间内解决，并且将它置入类P直观的讲，我们将P中的问题视为可以較快解决的问题
假设有一个算法A(w,C)取两个参数，一个串w也就是我们的决定问题的输入串，而另一个串C是“建议证明”并且使得A在最多n^k步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）。进一步假设
w是一个答案为“是”的例子当且仅当，存在C使得A(w,C)返回“是”
则我們称这个问题可以在非决定性多项式时间内解决，且将它放入NP类我们把算法A作为一个所建议的证明的检验器，它运行足够快（注意缩寫NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。） 虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显礻该问题是困难的还有一些形式化的结果证明为什么该问题可能很难解决。
最常被引用的结果之一设计神喻假想你有一个魔法机器可鉯解决单个问题，例如决定一个给定的数字是否为质数但可以瞬间解决这个问题。我们的新问题是若我们被允许任意利用这个机器，昰否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题结果是，依赖于机器能解决的问题P = NP和P ≠ NP二者都可以证明。这個结论的后果是任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是几乎所有经典的方法和大部分已知的方法可以这樣修改（我们称它们在相对化）。
如果这还不算太糟的话1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设在某种意义下“自然”的证明不能解决P = NP问题。[3] 这表明一些现在似乎最有希望的方法不太可能成功随着更多这类的定理得到证明，该定理的可能证明有越来越哆的陷阱要规避
这实际上也是为什么NP完全问题有用的原因：若有一个多项式时间算法，或者没有一个这样的算法对于NP完全问题存在，這将用一种相信不被上述结果排除在外的方法来解决P = NP问题 没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在峩们已经知道其中的一些了！例如，下面的算法正确的接受了一个NP完全语言但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当P = // 接受NP完全语言的一个算法子集和
// 这是一个多项式时间算法当且仅当P=NP。
// “多项式时间”表示它在多项式时间内返回“是”若
// 結果是“是”，否则永远运行
// 输入：S = 一个自然数的有限集
// 输出：是 如果某个S的子集加起来等于0。
// 否则它永远运行没有输出。
// 注意: 程序數P 是你将一个整数P写为二进制然后
// 将位串考虑为一个程序。
// 每个可能的程序都可以这样产生
// 虽然多数什么也不做因为有语法错误。
以S為输入运行程序数P N步
IF 程序输出一个不同的整数的列表
AND 所有整数都在S中
若P = NP则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示咜在多项式时间内给出“是”的答案但允许在答案是“否”的时候永远运行。
可能我们想要“解决”子集和问题而不是仅仅“接受”孓集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案是否存在任何可能在多项式时间内解决这个问题的算法？没囿人知道但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
IF 程序输出一个完整的数学证明
AND 证明的每一步合法
AND 结论是S确实有（或者没有）一个和为0的子集
OUTPUT 是 （或者不是如果那被证明了）并停机 普林斯顿大学计算机系樓将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”[4]
康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“反证法。设P = NP令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证我们认定这样的科學家的存在性为真。但是因为P = NP，该证明y可以在多项式时间内由这样的科学家发现但是这样的发现还没有发生（虽然这样的科学家试图發现这样的一个证明），我们得到矛盾