开发者

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 开发者_如何学GoW) 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?


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.


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜