# 1. P、NP、NPC 和 NP-Hard 问题的通俗化解释和详细区分
- 多项式级的复杂度：
O(1), O(n), O(n^2), O(lg(n)), O(nlg(n)) - 非多项式级的复杂度：
O(2^n), O(n!)
- P 问题：可以在多项式时间内找到解决该问题的算法
- NP 问题：可以在多项式的时间里验证该问题的一个解
- NPC 问题：是一个 NP 问题，并且所有的 NP 问题都可以约化到该问题
- NP-hard 问题：不一定是一个 NP 问题，但所有的 NP 问题都可以约化到该问题
注意：时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
# 2. 规约/约化
问题A可以约化为问题B，称为“问题A可规约为问题B”，可以理解为问题B的解一定就是问题A的解，因此解决A不会难于解决B。由此可知问题B的时间复杂度一定大于等于问题A。
比如：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。
# 3. 判断 NP 问题的技巧
- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
- 涉及“所有组合”的问题通常是NP完全问题。
- 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
- 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。