World's most popular travel blog for travel bloggers.

# [Solved]: Understanding details of NP-Hard definition

, ,
Problem Detail:

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

#### Answered By : David Richerby

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66179

3.2K people like this