Search code examples
notationcomputability

To prove something is NP-hard, why do you need to reduce to it from an NP-complete?


From wikipedia:

A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., L ≤ TH).

Why does the problem(call it W) being reduced from need to be NP-complete? Why can't it just also be NP-hard? It seems like what you care about W being "hard" not that its in NP.

Thoughts?


Solution

  • It can. In fact, your second paragraph implies the first paragraph.

    Assume NP-hard problem H is polynomially reducible to problem X. By definition, there exists an NP-complete problem C that is polynomially reducible to H. Since both reductions are polynomial, you can reduce C to X in polynomial time. Therefore, NP-complete problem C is reducible to X in polynomial time. Therefore problem X is NP-hard.