3 ms·

i'm confident i've hit an NP complete problem once. I don't remember the nitty gritty details, but it had something to do with optimal rendering of boxes on a s

by jfoutz 8y ago

i'm confident i've hit an NP complete problem once. I don't remember the nitty gritty details, but it had something to do with optimal rendering of boxes on a screen. kinda like bin packing. I've been asked a few times, but this one stands out. usually, my spidey sense kicks in, and i inform my manager what they're asking is hard, like multiple people for years with no guarantee of success hard. Mostly, they cut the feature. rarely they say keep poking at it for a while. I've probably messed that up a few times. But at least once, i felt that the problem was 3sat. i'm not a doctor. i'm not a moron. the problem seemed really hard, and i think i mapped it to 3sat. Perhaps i messed it up, and it wasn't really np-complete. Either way, it's not like i could look up the answer in a book. nobody wants to pay for original research. Very few people should do original research. I'm not a person that should do original research. I think i saved the company a lot of money by cutting the feature.

lifeisstillgood 8y ago
And this. Your value to the organisation for recognising a problem, arguing for a low cost solution and having the reputation to be believed is way larger than even a PhD researcher in the area who could have delivered an improved solution. By the way, packing problems are 70% optimal by putting the largest in first and keep going till the next largest won't fit. (It's like the old fart description - I cannot quote the source but the spider sense remembers the shape of the problem)
tasuki 8y ago
Did they really want optimal rendering of boxes? Would a "good enough" rendering of boxes be good enough to achieve whatever business goals?
- deleted 8y ago
  [deleted]
pyrale 8y ago
NP-hard problems are not always unfeasible. There are pretty good 3-sat solvers out of the box depending on your problem size. That being said, I don't know the details of your situation

by jfoutz 8y ago

lifeisstillgood 8y ago

And this. Your value to the organisation for recognising a problem, arguing for a low cost solution and having the reputation to be believed is way larger than even a PhD researcher in the area who could have delivered an improved solution. By the way, packing problems are 70% optimal by putting the largest in first and keep going till the next largest won't fit. (It's like the old fart description - I cannot quote the source but the spider sense remembers the shape of the problem)

tasuki 8y ago

Did they really want optimal rendering of boxes? Would a "good enough" rendering of boxes be good enough to achieve whatever business goals?

deleted 8y ago
[deleted]

pyrale 8y ago

NP-hard problems are not always unfeasible. There are pretty good 3-sat solvers out of the box depending on your problem size. That being said, I don't know the details of your situation