CODEWITHSUNDEEP
complexity-theoryanalysisnpnp-completenp-hard
Minimax
Minimax

Reputation: 131

Does Reducing P or NP instance to NP-Complete make that instance also NP-Hard?

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

Upvotes: 0

Views: 2422

Answers (1)

Dima Chubarov
Dima Chubarov

Reputation: 17169

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

Upvotes: 1

Related Questions