I need a very short and simple description for my doubts about some concept in following:
all NP-Complete problems can be reducible to all problems in NP-Hard.
any np-hard problem can be reducible to one NP-complete problem.
first is true and second is false.
I have three question:
what is the role of "all" words here?
why the first is true?
if we say "some np-hard problem can be reducible to one NP-complete problem. for the second fact, now is it correct?
I think better wording will be "any NP-complete problem can be reduced to any NP-hard problem" and "any np-hard problem can be reduced to an NP-complete problem".
The first is true, because all NP-complete problems are in NP, and NP-hard problems are exactly such that any problem from NP can be reduced to them.
The second is false, because NP-hard problem can be harder than NP. For example, Halting problem is NP-hard (any computable problem can be reduced to Halting problem), but it's not in NP, and thus can't be reduced to NP-complete problem.