归约与 NP 完全性
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| reduction/rɪˈdʌkʃn/ | 归约 | guī yuē |
| NP-completeness | NP 完全性 | NP wán quán xìng |
穿着别人衣服的问题
- 归约 reduction $A \le_p B$ 是把 A 实例多项式翻译成 B 实例的转换器：有了 B 解器就解了 A。NP 完全性 NP-completeness = 属于 NP + 所有 NP 问题都可归约到它。
{exercise:uni-cs1006-reduction}
练习
归约 A 到 B 带来——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
翻译器把 A 实例映成 B 实例：解了 B 就解了 A。
两步硬度证明
- 证 $B$ NP 难：选一个已知 NP 完全的 $A$，构造多项式翻译 $A \to B$。难度流向你的问题——把已知的难题归约到你的问题上。
- 课程链：SAT $\to$ 3-SAT（子句拆分）、3-SAT $\to$ CLIQUE（三角构件）、CLIQUE $\to$ VERTEX-COVER（取补图）。
{exercise:uni-cs1006-hardness}
练习
要证 B NP 难，应归约——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
难度流进你的问题：已知难题到你。
方向即内容
- 团到覆盖具体版：$G$ = 三角 ABC 加孤立 D 有 3 团；补图边恰为 A–D、B–D、C–D，而 {D}——规模 $n - k = 1$——全盖。
- 把你的问题归约到 SAT 不证明任何难度——箭头指向轻松的一侧。NP 意为多项式可验证；P 含于 NP。
{exercise:uni-cs1006-direction}
练习
把你的问题编码成 SAT 证明——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
箭头指向轻松一侧：你的问题归约到 SAT。