Why does the formal procedure prove NP-Completeness? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 9 years ago.

Improve this question

I know how to show that a problem X is NP-Complete.

1. Show that X ∈ NP.
2. Show Y ≤p X: show a problem Y known to be NP-Complete can be reduced to X in polynomial time.

However, I'm stuck on why this procedure proves that X is NP-Complete. Could someone explain this in a relatively simple way?

Answer 1

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:

1. The problem is in NP (same as your 1)
2. The problem is NP-Hard

You can show (2) by 2 ways:

1. Prove directly that there is a reduction from every problem in NP to it (hard to do)
2. Show a reduction from any known NP-Hard problem to your problem.

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.