computation-theory - NP和3-SAT和一个事实

Question

任何专家都可以帮助我为什么这句话是真的？

如果 L ∈ NP 并且 L ≤<sub>p 3−SAT（即：在多时间内将 L 减少为 3-SAT），则 L 是 NP-Complete。

Answer 1

这种说法是错误的。由于 3SAT 是 NP 完全的，所以 NP 多项式时间中的每个问题都会减少到 3SAT，因此如果您在 NP 中选择任何语言，那么多项式时间会减少到 3SAT。特别是，如果您选择空语言∅，已知它不是 NP 完全的，那么 ∅ ∈ NP 并且 ∅ 减少 toe 3SAT，但 ∅ 不是 NP 完全的。

希望这可以帮助！