NP 和 3-SAT 以及一个事实
NP and 3-SAT and One Facts
任何专家都可以帮助我为什么这句话是正确的？
if L ∈ NP and L ≤p 3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete.
这个说法是错误的。由于 3SAT 是 NP-complete，every 问题在 NP 多项式时间减少到 3SAT，所以如果你选择 any 语言在 NP，那么它将多项式时间减少到 3SAT。特别是，如果您选择已知不是 NP 完全的空语言 ∅，则 ∅ ∈ NP 和 ∅ 减少了脚趾 3SAT，但 ∅ 不是 NP 完全的。
希望对您有所帮助！
任何专家都可以帮助我为什么这句话是正确的？
if L ∈ NP and L ≤p 3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete.
这个说法是错误的。由于 3SAT 是 NP-complete，every 问题在 NP 多项式时间减少到 3SAT，所以如果你选择 any 语言在 NP，那么它将多项式时间减少到 3SAT。特别是，如果您选择已知不是 NP 完全的空语言 ∅，则 ∅ ∈ NP 和 ∅ 减少了脚趾 3SAT，但 ∅ 不是 NP 完全的。
希望对您有所帮助！