big-ocomplexity-theorynp-completenp-hard

Is an NP-complete problem also an NP-hard?


We can say that an NP-complete problem is one which is in NP and in NP-hard, but can we argue exclusively that a problem is NP-hard solely due to the fact that it is NP-complete.

Example: I reduce an NP-complete problem a to a problem b. Therefore, problem b is now proven to be NP-complete. Can I actually say that it is also NP-hard?


Solution

  • The definition of NP completeness is:

    A problem Q is NP-complete if and only if Q is in NP and Q is NP-hard.

    Therefore, yes, we can most definitely say that any NP-complete problem is NP-hard, by definition.

    Note that you have a slight misstatement in your question:

    Example: I reduce an NP-complete problem a to a problem b. Therefore, problem b is now proven to be NP-complete.

    The above conclusion only holds if you've shown b to be in NP. If b is "harder" than NP, then it is not NP-complete. Note, however, that the reduction is enough to prove that b is NP-hard.