为什么所有的NP完全问题都可以归结为3-SAT

Question

当我试图弄清楚为什么停止问题是NP难的时，我发现了这一点。然而，有一句话让我困惑

我们首先注意到，所有NP完全问题都可归结为3SAT。

为什么所有NP完全问题都可以归结为3-SAT？

希望你的答案：-(

Answer 1

根据定义，NP-完全问题X具有每个问题Y&inNP归约为X。(这就是NP-硬度的含义。(类似地，根据定义，每个NP-完全问题都在NP中。把这两者放在一起，每个NP-完全问题都会减少到彼此，所以所有NP-完全问题减少到3SAT。