NP-hard does not mean hard (2017)
jeremykun.com
NP-hard does not mean hard (2017)
1–10 of 101 posts
Re: NP-hard does not mean hard (2017)
#2Hey, I vouched for your submission. Just wanted to let you know that there seems to be some issue with your account causing your submissions to be automatically flagged. You may want to contact HN moderators (hn@ycombinator.com) about that.
Re: NP-hard does not mean hard (2017)
#3Hey, I vouched for your submission. Just wanted to let you know that there seems to be some issue with your account causing your submissions to be automatically flagged. You may want to contact HN moderators (hn@ycombinator.com) about that.
I've fixed it now. Thanks for watching out for a fellow user!
Re: NP-hard does not mean hard (2017)
#4[deleted]
Re: NP-hard does not mean hard (2017)
#5Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.
Re: NP-hard does not mean hard (2017)
#6Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.
[deleted]
Re: NP-hard does not mean hard (2017)
#7Corollary: P does not mean easy.
Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set.
Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it. But just because something is in P doesn't mean that you want to be solving it with a polynomial time algorithm on a regular basis.
Re: NP-hard does not mean hard (2017)
#8Look into the formal verification community, where PSPACE-complete is "easy" and undecidable is normal.
Re: NP-hard does not mean hard (2017)
#9Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.
From what I remember:
NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time.
NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct.
NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it means if you find a solution for any NP-Complete problem, you have found a solution for all of them. Finding an NP-Complete solution always seemed rather rather optimistic to me, but computer science professors obsessed over these problems.
Caveat: It has been more than 20 years since I was quizzed on this stuff, so it might be wrong.
Re: NP-hard does not mean hard (2017)
#10Look into the formal verification community, where PSPACE-complete is "easy" and undecidable is normal.
Hopefully they don’t need to deal with “big data”