4

When I tried to figure out why halting-problem is NP-hard, I found this. However, there is a statement confuse me

We begin by noting that all NP-complete problems are reducible to 3SAT.

Why all NP-Complete problems can be reducible to 3-SAT?

Hope for your answer :-)

Zheyuuu
  • 151
  • 1
  • 12

1 Answers1

3

By definition, an NP-complete problem X has the property that every problem Y ∈ NP reduces to X. (This is what NP-hardness means.) Similarly, by definition every NP-complete problem is in NP. Putting these two together, every NP-complete problem reduces to every other, so all NP-complete problems reduce to 3SAT.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    is there a resource showing reductions from common NP-Complete problems to 3SAT? Ie. clique, vertex cover, independent set, subset sum, knapsack – mLstudent33 Apr 13 '21 at 18:52
  • 1
    I’m not familiar with a standardized resource for doing that, but I imagine that if you search “SAT Solver” you might find some links? – templatetypedef Apr 13 '21 at 18:53