5 ms·
I read a LOT about that problem at one point and seem to recall that someone had proven that a naive solution was only on the order of 17% less than optimal in
by DannoHung 17y ago
I read a LOT about that problem at one point and seem to recall that someone had proven that a naive solution was only on the order of 17% less than optimal in the worst case.
- roundsquare 17y agoThere's a lot of results like that. You can do some pretty fast algorithms that are provably "not so bad" compared to the optimal solution and run in polynomial time. The problem is that you generally can't combine these with problem reduction to get a "not so bad" solution to a different problem (at least as far as I know).
- nopassrecover 17y agoI'm confident that if there is a solution it will be on the order of trickey of Godel's Incompleteness Theorem. Something like feeding the property of validation back into the algorithm somehow. But what do I know..
- roundsquare 17y agoI'm not talking about actually solving P vs NP. I'm talking about approximation algorithms. My point is this... lets say you have two problems A and B. Even if you have an approximation algorithm that solves A to within 50% of optimal, then reducing B to A, solving A and converting to solution back to one for B won't necessarily a 50% approximation for B. (Sorry if I missed your point and this explanation is redundant).
- nopassrecover 17y agoYeah definitely. There's a lot of potential in approximation (something humans are naively good at for NP complete). My little irrelevant point was that approximations hold an incremental solution (as you've noted along with the fact they aren't necessarily transposable) but are unlikely to lead to a revolutionary solution.