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 :-)
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.