undefined | Better HN

0 pointsngruhn2y ago0 comments

I’m saying this because most people got from their CS degree that NP hardness is practically a death sentence. But it‘s really not true. Even if the problem is proven to be NP hard (or worse) and every previous approach has failed. There can still be some trick or technique (non heuristic!) that brings a breakthrough. Maybe you still wait 10^whatever years for a solution in some cases. But if you get an answer in seconds in 99.9% of cases then its not a big deal in practice.

Even the famous SAT problem can almost be considered solved nowadays with the solvers we have.

0 comments

baq2y ago

The true benefit of being able to tell NP-complete/NP-hard from the garden variety bucket-o-bytes moving is not in giving up when you encounter them, as you correctly identified, but in knowing that even attempting an optimal solution is futile and proceeding to looking for approximate solutions to the business problem more or less instantly.

People unfamiliar with the matter may attempt to solve the problem, might even get rewarded for effort and hard work if management is also unfamiliar with the matter. Maybe it's fine though...?

travisjungroth2y ago

Optimal is overblown for business problems in general. Knowing there’s a mathematically optimal solution, people want it. Even if it’s practically impossible to get. It feels like if you have the optimal, you don’t have to consider trade offs (not usually true).

Having a solution within 1% of optimal with ten nines of confidence is usually indistinguishable.

Anyone ever notice how these CS problems are rarely famous business problems? It’s because the pure problems don’t usually matter and the approximate versions are usually quite easy. You almost never need the shortest route for a salesman, or need to pick a secretary with no chance of going back.

baq2y ago

I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)

3 more replies

jacquesm2y ago

Yes, exactly this. You don't need the optimal solution in most cases, you just need a solution, and if it is 9x% there then the optimum solution can be approximated by burning more cycles but from an economics perspective you may well already have a viable solution in hand.

fbdab1032y ago

It also depends on if you actually need the optimal solution. Getting a solution in your time budget, even if not guaranteed to be optimal, can be appropriate for many problems.

imtringued2y ago

>I’m saying this because most people got from their CS degree that NP hardness is practically a death sentence. But it‘s really not true.

It's a death sentence for economists, since they rely on every agent optimizing the entire economy of 8 billion agents in real time. 3 hours for 8 million variables isn't real time.

j / k navigate · click thread line to collapse

0 pointsngruhn2y ago0 comments

Even the famous SAT problem can almost be considered solved nowadays with the solvers we have.

0 comments

baq2y ago

People unfamiliar with the matter may attempt to solve the problem, might even get rewarded for effort and hard work if management is also unfamiliar with the matter. Maybe it's fine though...?

travisjungroth2y ago

Having a solution within 1% of optimal with ten nines of confidence is usually indistinguishable.

baq2y ago

I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)

3 more replies

jacquesm2y ago

fbdab1032y ago

It also depends on if you actually need the optimal solution. Getting a solution in your time budget, even if not guaranteed to be optimal, can be appropriate for many problems.

imtringued2y ago

>I’m saying this because most people got from their CS degree that NP hardness is practically a death sentence. But it‘s really not true.

It's a death sentence for economists, since they rely on every agent optimizing the entire economy of 8 billion agents in real time. 3 hours for 8 million variables isn't real time.

j / k navigate · click thread line to collapse