0

If a Problem X lying in P or NP can be reduced to NP-Complete, is that problem X automatically an NP-Hard problem?

Minimax
  • 121
  • 1
  • 5
  • 20
  • Possible duplicate of [What are the differences between NP, NP-Complete and NP-Hard?](https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard) – Dima Chubarov May 28 '18 at 07:59

1 Answers1

1

Quick reply: No, it does not.

Recall the definition of NP-hard problems.

A problem X is NP-Hard if every problem in NP can be polynomially reduced to X.

If on the other hand a problem X can be polynomially reduced to some NP-complete problem Y, it means that Y is at least as hard as X, not the other way around.

Finally, if an NP-complete problem Z can be polynomially reduced to X, then indeed X is NP-hard as every problem W in NP can be reduced to Z and by combining the two reductions we can reduce W to X, so the definition is satisfied.

Q: If a Problem X lying in P or NP can be reduced to NP-Complete, is that problem X automatically an NP-Hard problem?

A: No

Q: If a Problem X lying in P or NP is such that an NP-Complete problem can be reduced to it, is that problem X automatically an NP-Hard problem?

A: Yes

Dima Chubarov
  • 16,199
  • 6
  • 40
  • 76