3 ms·

Can someone explain what is NP-Hard in a few sentences?

by fiatjaf 11y ago

eli 11y ago
https://www.reddit.com/r/explainlikeimfive/comments/1glcly/eli5_np_nphard_npcomplete/ https://www.reddit.com/r/explainlikeimfive/comments/1glcly/e...
Datsundere 11y ago
Problems are solved with algorithms. Algorithms are either efficient or not efficient. Algorithms that are efficient can be solved in polynomial time (i.e. time can be estimated with Big Oh notation). So they have a deterministic algorithm. For NP problems, you only have a brute force solution that is inefficient. https://simple.wikipedia.org/wiki/P_versus_NP https://simple.wikipedia.org/wiki/P_versus_NP
simonsarris 11y ago
Without using any math terms at all: Suppose you've got a list of numbers: 5, 11, 26, 13, 215, 55, 68, 99, 3, 7, 41 And I ask: "Do any of these numbers together add up to 126? You might have to try every combination of numbers to get an answer. It can be very slow to do, trying every single combination (imagine a list with thousands of numbers, and a very long goal number). Maybe there are no combinations! But once you have an answer: 11 + 13 + 99 + 3 = 126 It is very easy to verify that the provided answer is correct (are all those numbers in my list? Yes, verified!) Compare that problem to this one: Is this list of numbers in ascending order? 4, 7, 11, 22, 6, 35 The answer is "No, because of the 6." Finding the answer is much faster because you can do it on one read-through of the list. You aren't checking a huge number of potential combinations or anything. The first problem is in the class of problems called NP-Hard. Oof. Getting lengthy so I'll shush here. Hope that gives you an intuitive feel for it.
- fryguy 11y ago
  That's just NP though. NP-hard means that if you have an algorithm that runs in NP to an HP-hard, you can solve all of them (with a polynomial-time transformation).
- fiatjaf 11y ago
  Thank you!
sgrove 11y ago
By far my favorite explanation of it all, starts simple and explores it very well: https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s

Can someone explain what is NP-Hard in a few sentences?

by fiatjaf 11y ago

Can someone explain what is NP-Hard in a few sentences?

eli 11y ago

https://www.reddit.com/r/explainlikeimfive/comments/1glcly/eli5_np_nphard_npcomplete/ https://www.reddit.com/r/explainlikeimfive/comments/1glcly/e...

Datsundere 11y ago

Problems are solved with algorithms. Algorithms are either efficient or not efficient. Algorithms that are efficient can be solved in polynomial time (i.e. time can be estimated with Big Oh notation). So they have a deterministic algorithm. For NP problems, you only have a brute force solution that is inefficient. https://simple.wikipedia.org/wiki/P_versus_NP https://simple.wikipedia.org/wiki/P_versus_NP

simonsarris 11y ago

Without using any math terms at all: Suppose you've got a list of numbers: 5, 11, 26, 13, 215, 55, 68, 99, 3, 7, 41 And I ask: "Do any of these numbers together add up to 126? You might have to try every combination of numbers to get an answer. It can be very slow to do, trying every single combination (imagine a list with thousands of numbers, and a very long goal number). Maybe there are no combinations! But once you have an answer: 11 + 13 + 99 + 3 = 126 It is very easy to verify that the provided answer is correct (are all those numbers in my list? Yes, verified!) Compare that problem to this one: Is this list of numbers in ascending order? 4, 7, 11, 22, 6, 35 The answer is "No, because of the 6." Finding the answer is much faster because you can do it on one read-through of the list. You aren't checking a huge number of potential combinations or anything. The first problem is in the class of problems called NP-Hard. Oof. Getting lengthy so I'll shush here. Hope that gives you an intuitive feel for it.

fryguy 11y ago
That's just NP though. NP-hard means that if you have an algorithm that runs in NP to an HP-hard, you can solve all of them (with a polynomial-time transformation).
fiatjaf 11y ago
Thank you!

sgrove 11y ago

By far my favorite explanation of it all, starts simple and explores it very well: https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s