Search code examples
computation-theoryturing-machinesnp-completenpdecidable

NP and 3-SAT and One Facts

any expert could help me why this sentence is True?

if L ∈ NP and L ≤p 3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete.

Solution

  • This statement is false. Since 3SAT is NP-complete, every problem in NP polynomial-time reduces to 3SAT, so if you choose any language in NP, then it will polynomial-time reduce to 3SAT. In particular, if you choose the empty language ∅, which is known not to be NP-complete, then ∅ ∈ NP and ∅ reduces toe 3SAT, but ∅ isn't NP-complete.

    Hope this helps!