Search code examples
complexity-theorynp-completenpnp-hard

reducing to np hard

Wiki says that when you convert a np complte problem in poly time to A , A is np hard. see http://en.wikipedia.org/wiki/NP-hard

But the pdf below says that when you convert a np hard problem to problem A in polynomial time , A is np - hard http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf

Which one should i believe?

Solution

  • Both. NP-complete is a subset of NP-hard; NP-complete problems are, by definition, NP-hard. If you're going to remember only one statement, remember the latter: if a problem in NP-hard can be reduced to a problem A in polynomial time, then A is NP-hard as well.

    For what it's worth, NP-hardness refers to the case in which any problem in NP can be reduced to the problem in polynomial time. NP-completeness refers to the case in which a problem is both in NP and in NP-hard.