理论与进阶专题
NP 完全性
NP 完全性是给一族问题贴的标签，这族问题共享一种奇特的双重性格：给出的答案可以被快速核验，但要找到这个答案却似乎得在一个巨大的空间里搜索、且没有已知的捷径。「NP」是这样一类问题：它们的「是」答案附带一份证书，你能在多项式时间内验证。数独是最亲切的画面：确认一张填好的盘面是否合法只要几秒，可从空盘解起却可能令人头疼。NP 完全问题就是 NP 里最难的那些。
它们的特殊之处由「归约」刻画。一个问题是 NP 完全的，当且仅当它属于 NP，且 NP 里的所有其他问题都能高效地变换成它——于是只要你为某一个 NP 完全问题找到了真正快（多项式时间）的算法，就能把任何 NP 问题翻译成它并一并快速解决。这正是它们被称为「NP 里最难」的原因：它们靠这些翻译彼此牢牢绑在一起。著名成员有布尔可满足性（SAT）、旅行商问题的判定版本（是否存在一条短于 k 的回路？）、图着色，以及背包问题。
它的现实意义令人清醒，却很有用。如果你证明了自己的问题是 NP 完全的，这并不是说它不可能解——而是说当今地球上没人知道一个能良好扩展的方法，因此死磕一个快速的精确算法多半是白费力气。你转而该拿起别的工具：能逼近最优解的近似算法、在实践中表现良好的启发式、对小规模输入可行的精确求解器，或利用你手上数据的特殊结构。这个标签是给你的努力改道，而非叫停。
// SAT, e.g. (a OR !b) AND (b OR c)
// Verifying a proposed assignment is fast:
bool satisfies(const Formula& f, const Assignment& a) {
for (const Clause& c : f.clauses)
if (!c.isTrueUnder(a)) return false; // O(total literals)
return true;
}
// But finding a satisfying assignment among 2^n possibilities
// has no known polynomial-time algorithm.核验一个候选解是 O(公式大小)；搜遍所有赋值则是指数级。
NP 完全不等于「已证明不可能」——它意味着没有已知的快速算法，而只要为其中任何一个找到快速算法，就能一举攻破全部。
又称
另见