6.8.1. SAT 到 3-SAT 的归约¶

下面的幻灯片表明，公式可满足性（ SAT ）问题的任意一般实例都可以在多项式时间内归约为 3 CNF 可满足性（ 3-SAT ）问题的一个实例。

Settings

Saving...
Server Error
Resubmit

这个归约有助于为 3-SAT 提供 NP 完全性证明。

接下来的练习会让你亲手重现 3SAT 是 NP 完全的证明。这将有助于确认你是否理解这一过程。