17. 3-SAT 到哈密顿回路的归约¶
17.1. 3-SAT 到哈密顿回路¶
下面的幻灯片表明，3-CNF 可满足性（3-SAT）问题的一个实例可以在多项式时间内归约为哈密顿回路（Hamiltonian Cycle）问题的一个实例。 对构造作一个微不足道的改动，就能实现从 3-SAT 到哈密顿路径（Hamiltonian Path）问题的归约。
这个归约有助于为哈密顿回路（Hamiltonian Cycle）问题提供 NP 完全性证明。 .. odsascript:: AV/NP/threeSATtoHCCON.js
