views:

82

answers:

2

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?

+2  A: 

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.

Mehrdad Afshari
O_o good point! Thanks, that answers my question. :D
UnknownGuy
A: 

If you can polynomially reduce an NP-hard problem to your problem that's sufficient to prove NP-hardness of your problem. However, a specific NP-hard problem may not be polynomially reducible to your problem even though it is NP-hard itself.

Furthermore, you do not have to prove NP-hardness by reduction you can also prove it directly.

Peter G.