14. SAT 到 3-SAT 的归约¶
14.1. SAT 到 3-SAT 的归约¶
下面的幻灯片表明，公式可满足性（ SAT ）问题的任意一般实例都可以在多项式时间内归约为 3 CNF 可满足性（ 3-SAT ）问题的一个实例。
这个归约有助于为 3-SAT 提供 NP 完全性证明。
下面的练习给你一个机会，让你重现 3SAT 是 NP 完全的证明。 这将有助于确认你是否理解这一过程。
| 关于 « 13. Circuit SAT 到 SAT 的归约 :: 目录 :: 15. 3-SAT 到团的归约 »
下面的幻灯片表明，公式可满足性（ SAT ）问题的任意一般实例都可以在多项式时间内归约为 3 CNF 可满足性（ 3-SAT ）问题的一个实例。
这个归约有助于为 3-SAT 提供 NP 完全性证明。
下面的练习给你一个机会，让你重现 3SAT 是 NP 完全的证明。 这将有助于确认你是否理解这一过程。
隐私 | | 许可协议 « 13. Circuit SAT 到 SAT 的归约 :: 目录 :: 15. 3-SAT 到团的归约 »
