9.17.1. 3-SAT 到哈密顿回路¶

下面的幻灯片表明，3-CNF 可满足性（3-SAT）问题的一个实例可以在多项式时间内归约为哈密顿回路（Hamiltonian Cycle）问题的一个实例。对构造作一个简单的改动，就能实现从 3-SAT 到哈密顿路径（Hamiltonian Path）问题的归约。

Settings

Saving...
Server Error
Resubmit

这个归约有助于为哈密顿回路（Hamiltonian Cycle）问题提供 NP 完全性证明。