关于 P 与 NP 问题的简单说明：
假设你正在为 400 名大学生组织住宿，但是空间有限只有 100 名学生能在宿舍里找到位置。更复杂的是还给了你一份不相容学生的名单，并要求在你的最终选择中不要出现这份名单中的任何一对。
这是计算机科学家称之为 NP 问题的一个例子，因为很容易检查一个同事提出的一百个学生的给定选择是否令人满意，然而从头开始生成这样一个列表的任务似乎太难了以至于完全不切实际。
事实上从 400 名申请者中选择 100 名学生的方法总数比已知宇宙中的原子数量还要多！这类其答案可以被快速检查，但是通过任何直接的程序需要不可接受长度的时间来解决，比如 300 年或者更多…
斯蒂芬·库克和列昂尼德·莱文在 1971 年独立地提出了 P (即容易找到)和 NP (即容易检查)问题。
多项式时间
这是一个多项式的表达式，对于计算机来说，其时间复杂度为 。但是世界上不止是有多项式时间这么简单，比如还有指数函数形式的 。对于计算机来说，问题的难度并不是它主观去进行判断的，计算机做的只是将一个个问题拆分成为一个个步骤去完成，衡量其难度其实也就是计算步骤的次数以及时间来决定的，即执行时间越长的问题通常会比较难。
显而易见，多项式时间内能解决问题和不能的差距有多大。
P 问题
easy to find
即多项式时间内可解决的问题（当然在多项式时间是可验证的）
比如，计算 1-1000 的连续整数之和
NP 问题
easy to check
非确定性多项式时间内可解决的问题
比如，计算地球上所有原子个数之和，如果答案是 300 ，那显然是错误的。
还有著名的旅行商问题（TSP）：
旅行推销员问题 Travelling salesman problem 是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个 NP-Hard 问题，在运筹学和理论计算机科学中非常重要。
最早的旅行商问题的数学规划是由 Dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在 1% 内。
我们都知道在城市规模比较小时我们可以进行穷举来确定最优的路线，但是经过几次穷举我们发现穷举复杂度是 O(n!) 。
NPC 问题
从特征上看，我们可以知道 P 类问题属于 NP 问题，因为 P 类问题属于 NP 类问题中可在多项式时间验证并解决的问题，可以简单认为 P 类问题属于特例最基本简单的 NP 问题。
P 类问题是在我们目前能力范围内的，但是 NP 类问题要寻找最优解可能超越多项式时间，我们知道 P 类问题属于 NP 类问题。那么 NP 类问题是否可以归类为 P 类问题呢？
这，就是 P=NP 问题所要表达的东西：是否所有 NP 类问题都可以在多项式时间内解决并验证，也就是转化为 P 类问题。
当前阶段，大家的共识基本就是 P=NP 是不成立的，即至少存在一个 NP 类问题是无法在多项式时间内解决的。理由是什么，归功于 NPC 问题的发现。
NPC 问题 Non-deterministic Polynomial complete problem 又称 NP 完全问题，NPC 问题就是大量的 NP 问题经过归约化 (Reductions) 而发现的终极 boss NP 问题。
这里我们给出一份课件 。
归约化是解决复杂问题的一种思路工具，课件中展示了将问题 Y 归约化到问题 X 的过程，其中提到了多项式归约，如果我们找到了问题 X 的多项式时间解法，那么我们有理由相信问题 Y 同样可以找到多项式时间解法。
同时，归约化具备传递性：问题 A 可归约为问题 B ，问题 B 可归约为问题 C ，那么问题 A 可归约为问题 C ，正是基于这个特性我们才能把很多小的 NP 类问题串起来，最终出现 NPC 问题。
相比而言问题 X 比问题 Y 更难也更普遍，回到 NP 问题上来说， NP 问题的归约化就是去寻找一个终极 NP 问题，这个问题更普遍更难但是可以 cover 很多小范围的 NP 问题，这类终极 NP 问题就是 NP 完全问题。
- NPC 问题属于 NP 问题
- 对于所有 NP 问题都可以归约化到它
NP-Hard 问题
NP-Hard 问题是满足 NPC 问题定义的第二条，但不满足第一条，也就是说所有 NP 问题可以归约化到 NPH 问题，但是 HP-Hard 问题不一定是 NP 问题，所以 NPH 问题比 NPC 问题更难。
现在给出上述几个问题的的集合关系：
