Let me first try to briefly summarize NP-completeness:
A problem A is NP-complete if:
- you can verify it's solution in polynomial time
- you can reduce it to any other NP-complete problem in polynomial time
Since polynomial reduction is transitive, the second point is equivalent to saying that "you can reduce it to SAT in polynomial time".
The reduction is simply a function that compiles the starting problem to SAT and preserves it's solvability (in a bijective way).
In other words, to prove that a problem is NP-compelte, you must write a compilation function to SAT and also prove that every solution to the starting problem is also a solution to the destination problem in SAT. Furthermore you must also prove that any solution in the SAT version can be "decompiled" to a proper solution in the starting problem, so this is where the equivalence comes from and it's the reason that SAT is not really anyhow harder than other NP-complete problems.
The thing is, SAT has been heavily researched, so that's why you have extremely efficient SAT-solvers.
So if you want to solve an NP-complete problem, you can simply compile it to SAT, solve it with well-known SAT-solvers and "decompile" the solution to your starting problem
The other way around: to prove that X is NP-complete you need to reduce SAT(or any other known NP complete problem) to X.
The intuition here is that if you have a magic algorithm which solves X efficiently, you should be able to use this algorithm to solve any other NP problem, like SAT.
A problem A is NP-complete if:
- you can verify it's solution in polynomial time
- you can reduce it to any other NP-complete problem in polynomial time
Since polynomial reduction is transitive, the second point is equivalent to saying that "you can reduce it to SAT in polynomial time".
The reduction is simply a function that compiles the starting problem to SAT and preserves it's solvability (in a bijective way). In other words, to prove that a problem is NP-compelte, you must write a compilation function to SAT and also prove that every solution to the starting problem is also a solution to the destination problem in SAT. Furthermore you must also prove that any solution in the SAT version can be "decompiled" to a proper solution in the starting problem, so this is where the equivalence comes from and it's the reason that SAT is not really anyhow harder than other NP-complete problems.
The thing is, SAT has been heavily researched, so that's why you have extremely efficient SAT-solvers. So if you want to solve an NP-complete problem, you can simply compile it to SAT, solve it with well-known SAT-solvers and "decompile" the solution to your starting problem