I know how to show that a problem X is NP-Complete.
However, I'm stuck on why this procedure proves that X is NP-Complete. Could someone explain this in a relatively simple way?
NP Complete problem is defined to be a problem that is both NP-Hard and in NP (definition), so you basically need to show 2 things:
You can show (2) by 2 ways:
The thing is, reduction is transitive, so if you prove there is a reduction from some NP-Hard problem (let it be L1
) to your problem (Let it be L2
), you basically showed that there is a reduction from EVERY L
in NP to L1
(definition of NP-Hard), and from L1
to L2
(your reduction), thus the chain of these reductions (which is itself polynomial, neat things about polynoms), is a reduction by itself from every L
in NP to L2
(your problem).
In other words, since L <=p L1 <=p L2
for every L
, it follows that L <=p L2
for every L
as well, and this is the exact definition of NP-Hardness.
This way, you showed there is a reduction from every problem in NP to your problem, and this is the definition of NP-Hardness.
Since showing directly that there is a reduction from EVERY L
in NP to a language, it was done once on SAT (Cook-Levin theorem) [twice actually...], and now you can use reductions to increase the number of known NP-Hard Problems.