引言

对于学习计算机的学生来讲，在算法里面应该经常会接触到。
当然也有各种多项式时间复杂度: O(n) O(logn) O(nlogn) O(n2) O(n3)
在这里简单总结一下，P VS. NP 的一些基本概念

P问题

在一个由问题构成的集合中，如果每个问题都存在多项式级复杂度的算法，这个集合就是 P 类问题.
所白了就是给你一个集合，这个集合里面都是问题，而且都是简单的能够用上面的时间复杂度的组合解决的问题

NP问题

“NP”的全称为“Nondeterministic Polynomial”
NP 类问题指的是，能在多项式时间内检验一个解是否正确的问题。
所白了就是：给你一个问题，我不知道他是怎么求解的，但是我能够碰运气，盲猜一个解；并且我能够在引言的时间复杂度内检验我的解是否正确
例如：图染色问题，我们可以盲猜一个答案吧。哈密顿回路，也可以盲猜一个吧。

那么究竟 P 是否等于 NP呢？

首先，为什么要证明： P 是否等于 NP
因为NP类问题我们只能盲猜，我们不知道这类问题是否存在多项式解。如果能证明NP == P 我们就能证明了：对于这种很难的问题，肯定有多项式解，只是我们不知道。
为了证明这个问题：就引出了归约。
归约思想：NP问题有很多，难道我要一个个去证明等于P问题吗？？
我们可以吧问题转化一下，我们把NP问题中，最难的问题，NPC问题给找出来。
如果所有的NPC问题都有多项式解，那么 NP 就等于P
NPC问题： 图染色 、 旅行商问题

NP-hard问题

这里问题就是：连盲猜都不行的问题。你去验证一个答案都要不知道多少时间
例如：图灵停机问题