5 ms·
It is always fascinating how many problems that are simply stated are difficult to solve. Whenever I see something like this I try and think about what the rep
by dannyz 5y ago
It is always fascinating how many problems that are simply stated are difficult to solve. Whenever I see something like this I try and think about what the repercussions would be if an efficient algorithm did exist, and that helps to understand where the complexity is. In this case I believe there would be many problems in computational geometry involving Euclidean shortest paths that would be made trivial by an efficient algorithm here.
- lupire 5y agoThis problem is only hard when infinite precision is needed. It's trivial if you allow any tolerance on the scale that could exist in the Universe.
- Sharlin 5y agoHowever, it would be interesting to find some pathological examples of pairs of lists whose sums of square roots compare almost equal if only approximated to some reasonable precision, but diverge absurdly if the fully general algorithm is used, if such pairs even exist.
- vessenes 5y agoI am reasonably sure that this won’t happen, or said another way, a function that returns the minimum delta between any finite pairs of lists is a reasonably well behaved function wrt the length of the list and the size of the integers and doesnt just zoom off to infinitely close to zero ever. Said yet another way, the ways in which real numbers are dense is spooky and almost totally untied to how rationals work, and i do not believe you can get there from here using square roots.
- ChrisLomont 5y agoThis isn't true, which is why the problem lies in the complexity class listed in the article. Arbitrarily bad pathologies exist even for simple inputs.