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

Improve this question
$\endgroup$
2
  • 2
    $\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
    Commented Nov 18, 2016 at 8:46
  • $\begingroup$ The definition says "every problem", not "some problem" -- you got the quantification wrong in your last paragraph. $\endgroup$
    – chi
    Commented Nov 18, 2016 at 10:25

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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