# Understanding details of NP-Hard definition

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

• 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$. – skankhunt42 Nov 18 '16 at 8:46
• The definition says "every problem", not "some problem" -- you got the quantification wrong in your last paragraph. – chi Nov 18 '16 at 10:25

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.
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.