4
$\begingroup$

I am learning from this video: https://www.youtube.com/watch?v=eHZifpgyH_4 at 21:17 he talks about his definition of NP-Hard.

The definition is: X is NP-Hard if every problem y which belongs to NP reduces to X.

I watched that part of the video several times but don't understand it. In particular, here's one thing I don't get:

P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard? That would mean that y we just converted would have an NP-Hard solution but it is actually polynomial? Sorry if this is confusing. I hope I can word it better but it to me that definition only makes sense if they talk about NP problems that are not part of P

$\endgroup$
  • 1
    $\begingroup$ Every problem $Y \in NP$ means that no matter what $Y$ I give, if $X$ is $NP$-hard, then it should many-one reduce in polynomial time to $X$. So you can't just choose some $Y \in NP (\text{ or } P)$, reduce it to $X$ and claim that $X$ is $NP$-hard. The reduction should work for every $ Y \in P$. $\endgroup$ – skankhunt42 Nov 18 '16 at 8:46
  • $\begingroup$ The definition says "every problem", not "some problem" -- you got the quantification wrong in your last paragraph. $\endgroup$ – chi Nov 18 '16 at 10:25
5
$\begingroup$

The definition of NP-hardness for a problem $X$ is that every problem in NP reduces to $X$. Informally speaking, "$L$ reduces to $X$" means that if you could solve $X$, you could use that to solve $L$.

So, if $X$ is NP-hard, you can reduce all problems in NP, including the ones in P, to $X$. There's no contradiction here: $X$ is a hard problem, so saying that you can reduce a problem in P to $X$ is just saying, "If I could solve this hard problem, I could use that to solve a pretty easy problem." Sure, there are easier ways of solving that easy problem (that's why we call it an easy problem!) but all you've done is to show that there's a hard way to solve it, too.

P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard?

Maybe it's just inaccurate writing but you have the implication the wrong way around. If $X$ is NP-hard, then you can reduce a problem in P to $X$. The converse (if you can reduce a problem in P to $X$, then $X$ is NP-hard) is not true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.