Comment by tripzilch | Hacker News Reader

Comment by tripzilch | Hacker News Reader

Parent Full thread

> he forgets to mention that problems like the traveling salesman are for academics. The real world responds to the 'actual computing time of the traveling salesman + the traveling time' problem, i.e., if your exact solution is 10% better than the approximate solution but your computation time is 20 times longer so that the salesman can't even start actually traveling ;-) your best solution becomes suddenly your second best (plus many variations of it).

That doesn't really correspond to the real world problems that TSP occurs in.

While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design.

I'm not super-knowledgeable on either of those two, so I could be wrong, though.

Another point, which is not mentioned in the OP, is about graph problems. A lot of the intractable ones are really intractable only for a (large or infinite) class of degenerate inputs. But on the average case, solving it for "real world" graphs, for a lot of practical applications they can be solved in very reasonable time.

> While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design.

That is true, but it's the same that I was saying (and it's why I included the many variations at the end of the statement). Basically if you have to do something once and for all, then of course you can just solve it in some sort of educated brute force and you are probably fine. It's when you have to continuously adapt the solution to a changing network that you need to be fast, and in that case you need to consider that the computation time kinda together with the traveling time (of course it's more complicated than that and you need to include the cost advantages etc.).

I agree with the graph comment, even if we are growing in the amount of data to deal with those graphs, so there will be often more and more need of simplified or shortened solutions if you want them to run in an app on a phone, or on a server (but for a million requests).

Another example: Collision detection, finding the shortest path, and other physical-world problems are NP-Hard (as the number of dimensions increases, it gets really disgusting to find intersections and paths). But there are a large number of 3D games out there, because "3" is few-enough dimensions that we can compute it with modern computers really fast.

Reply on news.ycombinator.com