当问题很难时：P、NP 与难解性

快速求解与快速验证

你目前搭建的一切都运行在多项式时间内——代价形如 n、n log n 或 n^2，用[[big-o-notation|大 O 记号]]表示。拥有这样算法的问题类被称为 P（取自 polynomial，多项式）。这些就是我们认为「能高效求解」的问题：随着输入增长，工作量以一种可控、可预测的速率增长。

再来一个更微妙的类。NP 是这样一类问题：*如果有人递给你一个候选答案，你能快速验证它*（多项式时间）——哪怕找到那个答案本身可能很难。想象一幅巨大的拼图：拼好它也许要很久，但验证一幅已拼好的图是否正确只需一眼。P 中的每个问题也都在 NP 中（既然你能快速求解，当然也能快速验证），所以 P 包含在 NP 之内。

        +-------------------------- NP --------------------------+
        |   (answers are checkable fast)                          |
        |                                                         |
        |    +--------- P ---------+        +-- NP-complete --+    |
        |    | solvable fast       |        | hardest in NP   |    |
        |    | (sort, search, MST) |        | (SAT, TSP, ...) |    |
        |    +---------------------+        +-----------------+    |
        +---------------------------------------------------------+

  Open question:  is P = NP ?  i.e. does the P box secretly fill all of NP?

P 位于 NP 之内。两者是否其实相等——P 那一格是否悄悄填满了整个 NP——尚不可知。

NP 完全与那个未解之谜

NP 内部住着一个特殊家族：[[np-completeness|NP 完全]]问题。在一种精确的意义上，它们是 NP 中*最难*的问题——而且彼此紧紧相连。我们懂得如何把其中任意一个归约（reduce）为另一个：在多项式时间内，把问题 A 的一个实例改写成问题 B 的一个实例，使得解出 B 就解出了 A。正因为这张归约之网，只要有人为*其中某一个* NP 完全问题找到了快速（多项式时间）算法，那个算法立刻就能为*所有* NP 完全问题给出快速解法。

SAT（布尔可满足性）：给定一个逻辑公式，是否存在一组对变量赋真/假的取值，使整个公式为真？验证一个给定赋值是瞬时的；找出一个才是难处。SAT 是第一个被证明为 NP 完全的问题。
TSP（旅行商问题的判定形式）：给定一组城市和一个预算，是否存在一条在该预算内遍历所有城市的路线？验证一条路线的长度很容易；在天文数字般众多的路线中搜索却不然。
图着色、子集和、背包问题的判定形式，还有数以百计的其他问题，全都属于同一个俱乐部，由归约相连。快速解出一个，就解出了全部。

面对难题该怎么办

假设你已经断定你的问题是 NP 难的（至少和 NP 完全问题一样难）。这不是死胡同——而是一次改道。它告诉你别再追求一个完美、快速、精确的算法，而把力气花在真能见效的地方。你有几条诚实的出路。

近似（approximation）：接受一个可证明接近最优、但能被快速找到的答案。对许多 NP 难问题，存在多项式时间的算法，能保证比如「在最优解的 5% 以内」。
启发式（heuristics）：使用聪明的经验法则（贪心选择、局部搜索），即便没有保证，也能在典型输入上表现良好。它们驱动着现实中的路线规划器和排程器。
指数级但带剪枝的精确搜索：当实例不大时，一个边探索搜索空间、边砍掉无望分支的精确算法（分支定界，以及你在回溯中见过的剪枝），实践中往往能跑完，哪怕最坏情形是指数级。
限制问题：有时你实际面对的特例（一棵树而非一般的图、较小的整数权重）存在快速算法，尽管一般问题没有。