[codeflo]

Solvers aren't magic. But it turns out that many naturally occurring instances of NP-hard problems aren't the "really hard" instances that the NP-hardness proof depends on.

Solvers can also fail for really tiny problems. You simply have to try to figure out how hard (or how well adapted to the solver's heuristics) your particular problem instance is.

[ngruhn]

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.

[baq]

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...?

[travisjungroth]

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.

[baq]

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 :)

[theamk]

I would not be so sure.

What's the point of the theoretically perfect solution when the travel times are so unpredictable? The truck stops are 3-5 minutes apart on average (according to random reddit comment [0]), 1% of that is 3 seconds. Meanwhile a single missed light (say because some other vehicle was driving slow or UPS driver was guided into non-familiar route) can add more than a minute.

So something like a better way to arrange packages in truck, or better traffic preidiction model, would be much more useful than any TSP improvements.

[0] https://www.reddit.com/r/UPS/comments/89zw0h/how_long_does_o...

[ilyagr]

No individual truck would notice the difference. But averaged over many trucks and many days, it should result in a measurable change in gas spending.

[adwn]

The problem is that in practice, you don't have complete information, and the information you have is slightly incorrect. You also don't have a complete model, and the model you have is slightly incorrect.

[travisjungroth]

Throw on a few more decimal places if you like. The point is that in the physical world, “best” isn’t usually categorically different from “extremely close to best with high probability”.

[jacquesm]

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.

[fbdab103]

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.

[imtringued]

>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.

[jacquesm]

NP hard for a pathological case doesn't mean all practical cases are pathological. Many of the cases have optimal solutions in a reasonable amount of time without resorting to brute force because you can use structure in the dataset to limit the search space.

That you can construct a pathological case makes something NP hard for an arbitrary case but not for all cases. Compare with QS: it's very fast for most practical cases but you can construct a case where it performs quite bad, much worse than you'd expect given the name. But in practice that isn't all that relevant.

[thechao]

This reminds me of the random polynomial time bound for the simplex algorithm; an algorithm that is, naively, exponential time[1].

I seem to vaguely remember — this is ~17 years ago, now — that it's possible to "characterize" the really bad edge-cases for simplex and work around them (the whole point of the paper).

[1] https://cstheory.stackexchange.com/questions/2373/complexity...

[ur-whale]

> Solvers can also fail for really tiny problems.

What that tells me is that the current metric we use for problem complexity (e.g. big-o) is woefully inadequate at measuring the actual complexity of problems.

[jacquesm]

> the current metric we use for problem complexity (e.g. big-o) is woefully inadequate at measuring the actual complexity of problems.

The complexity of all problems. But big-O isn't the only complexity metric available.

It's extremely useful and very adequate in almost all cases, but it doesn't work well when the numbers are very small and the problems are part of a small subset of all available problems.

But those are edge cases. In practice those are fairly rare and when the datasets are small enough normally all solutions are more or less viable. But as soon as your data set is non-trivial big-O is the right tool to apply at the outset.

Right tool for the job... small dataset, tricky problem: big-O may not apply.

[kaba0]

Why would they be inadequate? They are a very good metric that lets one instantly recognize the way the problem’s certain properties change with respect to some other factor. Does it give a complete picture for everything? No. Why would it? But to say that they are woefully inadequate is just ridiculous.

[blt]

Lots of CS theorists are working on non worst case analysis and have been for some time. The CS research community recognizes the limitations of worst case.

It makes sense to teach worst case in undergrad classes because it's easier to understand and basically a prerequisite for other kinds of analysis.