Search code examples
complexity-theoryanalysisnpnp-completenp-hard

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?

Solution

  • 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