np-complete - 如何将 3COLOR 减少到 3SAT？

Question

我们知道 3SAT ≤p 3COLOR（即 3SAT 是多项式时间可简化为 3COLOR）。谁能给出一个简短的论据，为什么 3COLOR ≤p 3SAT？并给出一个实际的库克减少表明 3COLOR ≤p 3SAT 请。

score 2 · Accepted Answer

简短的回答是：由于 3SAT 是 NP 完全的，因此 NP 中的任何问题都可以简化为解决 3SAT 的实例（或显示它不可满足）。因此 3COLOR <=p 3SAT。

对于 3COLOR 到 SAT 的 pt 减少的构造，您可能会看到以下文档中的第 2 节（该主题与您的问题无关）：

1 回答 1