16.14. SAT 到 3-SAT 的归约¶
16.14.1. SAT 到 3-SAT 的归约¶
下面的幻灯片表明，公式可满足性（ SAT ）问题的任意一般实例都可以在多项式时间内归约为 3 CNF 可满足性（ 3-SAT ）问题的一个实例。
这个归约有助于为 3-SAT 提供 NP 完全性证明。
接下来的练习会让你亲手重现 3SAT 是 NP 完全的证明。这将有助于确认你是否理解这一过程。
| 关于 英文版 « 16.13. Circuit SAT 到 SAT 的归约 :: 目录 :: 16.15. 3-SAT 到团的归约 »
下面的幻灯片表明，公式可满足性（ SAT ）问题的任意一般实例都可以在多项式时间内归约为 3 CNF 可满足性（ 3-SAT ）问题的一个实例。
这个归约有助于为 3-SAT 提供 NP 完全性证明。
接下来的练习会让你亲手重现 3SAT 是 NP 完全的证明。这将有助于确认你是否理解这一过程。
