151–160 of 189 posts
> comparing sums of square roots is actually kind of a common subtask in eg computational geometry, so a bunch of their problems (including “shortest path through a graph in Euclidean space”!) are as-far-as-we-know extremely hard. But the question then arises: do we always need to solve these problems to their fullest precision? Can we perhaps leave some ambiguity, and let the system gracefully deal with it? E.g. I d…
It's hard to solve "generally", sure, but "practically", is there any application where extreme correctness of the algorithm would actually matter? Seems like if two huge lists sum to almost the exact same thing for tons of decimal places, then you can effectively treat them as equal. Sort of like how you only need like 5 or 6 digits of pi to get into orbit around the moon, etc.
Either prove, that the problem is PSPACE-complete (any PSPACE problem can be converted into it), or just say that your algorithm takes exponential time in polynomial space.
I'm not sure I understand the problem. If we only need to determine what set produces a sum of square roots that is larger, why can't we simply compare the sum of the original numbers? The square root of 2.0000001, for example, is larger than the square root of 2. The square root of X will be always be larger than the square root of Y if X is larger than Y. The real problem is calculating the precision of square root…
Consider [25] and [9, 9]. 25 > 18, but 5 < 6.
For example, just say 1/3. Easy right? 0.333333334 Wrong. It's impossible for a human or a computer to say the answer. NOT a CS issue. We can't combine random and ultimately repeating numbers. Each time you reduce a number via square root you will eventually reach an infinite response and thus it's impossible to solve, let alone with a binary computer system.
I would love the very first quantum computer to do 1/3. Just use up all the CPU and energy it has in a problem it can't solve. Forever in time.
Look not at the computer as the failure scenario but math in general. At some point you stop and round. When that happens, an error is introduced when you extend the answer beyond the rounding point. At some point you will fine an infinite answer and/or answers. I can write you a computer program to write a single infinite answer. Combining two of them produces the same infinite process.
Here is a better answer. Can we shift the base in a way that allows us to answer random questions like these?
It seems like this should just reduce to the question: given two natural numbers x and y represented by n bits how many bits are needed to represent the difference sqrt(y) - sqrt(x) so that it is non-zero when x != y. To see this suppose you compute each sqrt in both lists to k bits then group together the closest matching pairs from the two lists. Some of these pairs may have a difference of zero. Now increase k unt…
> At that point you know the answer, you just have to add up the differences. What if your sum in this step is zero?
This is not a computer science question. It's a math challenge. We simply rely on computers to do the math faster. I challenge any math person to solve this problem and/or provide a proof. Given that their equations will ultimately be so complex they will fail. For example, just say 1/3. Easy right? 0.333333334 Wrong. It's impossible for a human or a computer to say the answer. NOT a CS issue. We can't combine random…
This is not a computer science question. It's a math challenge. We simply rely on computers to do the math faster. I challenge any math person to solve this problem and/or provide a proof. Given that their equations will ultimately be so complex they will fail. For example, just say 1/3. Easy right? 0.333333334 Wrong. It's impossible for a human or a computer to say the answer. NOT a CS issue. We can't combine random…
"On the other hand, comparing the sums of fractions is pretty easy, because division is nice and well behaved. So the question is how complicated square roots are."
Earlier quoted context omitted.
Does that actually work? It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)). So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless t…
Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.