4 ms·
There'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 polynomia
by roundsquare 17y ago
There'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.