# NP 完全问题

1. 机器并不能解决所有的判定问题，比如停机问题

2. 3-SAT 问题
   - 文字，分句，公式
   - 3-SAT 问题即每个分句都是析取范式，每个析取范式中有 3 个文字，整个公式为析取范式的合取范式，判断是否存在一个赋值使得公式为真
   - 而每个 SAT 问题都可以转化为 3-SAT 问题
   - 3-SAT 问题求解很难，但是验证很容易

3. 独立集问题
   - 给定一个图，找到一个最大的独立集
   - 独立集即图中的一个顶点子集，任意两个顶点之间没有边

4. 基于独立集问题的判定/优化问题
   - 判定问题：给定一张图，判断是否有包括 $k$ 个顶点的独立集
   - 优化问题：给定一张图，找到一个最大的独立集

5. P 与 NP
   - P 问题：可以在多项式时间内 **解决** 的判定问题
   - NP 问题 (Non-deterministic Polynomial)：可以在多项式时间内 **验证某个正确答案** 的判定问题
   - co-NP 问题 (complementary NP)：可以在多项式时间内 **验证某个错误答案** 的判定问题
   - P 问题是 NP 问题的子集，即 P $\subseteq$ NP

6. 归约
   - 给定一个判定问题 $A$，和另一个判定问题 $B$，可以将 $A$ 问题的输入在多项式时间内转换为 $B$ 问题的输入，且 $A$ 问题的答案与 $B$ 问题的答案相同，称为 $A$ 可归约到 $B$，记为 $A \leqslant_p B$
   - 若 $A\leqslant_p B$，则 $B$ 问题的复杂度不会低于 $A$ 问题的复杂度

7. 3-SAT 问题可归约到独立集问题
   - 对于一个有 $k$ 个分句的 3-SAT 问题，构造一个图，图中有 $3k$ 个顶点，每个分句中的三个文字间两两连边，每个文字与所有它的否定文字连边
   - 则如果该图中有一个包含 $k$ 个节点的独立集，当且仅当该 3-SAT 问题有解

8. NPC 与 NP-hard
   - NP-hard 问题：所有 NP 问题都可以归约到该问题，即 NP-hard 问题的复杂度不会低于 NP 问题的复杂度
   - NPC 问题：既是 NP 问题，又是 NP-hard 问题

9. 要证明一个问题是 NP-hard，则只需将一个 NP-hard 问题归约到该问题即可

10. NPC 问题的证明
    - 证明该问题是 NP 问题
    - 证明该问题是 NP-hard 问题

11. NPC 问题两两可以互相归约

12. COOK 定理：3-SAT 问题是 NPC 问题