When I tried to figure out why halting-problem is NP-hard, I found this. However, there is a statement that confuses 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?
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.