np hard and np complete simple question

57 Views Asked by At

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:

  1. what is the role of "all" words here?

  2. why the first is true?

  3. if we say "some np-hard problem can be reducible to one NP-complete problem. for the second fact, now is it correct?

1

There are 1 best solutions below

0
On BEST ANSWER

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.