> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots
What is it?
A surprisingly hard CS problem: sums of square roots (2018)
11–20 of 189 posts
Re: A surprisingly hard CS problem: sums of square roots (2018)
#12This looks more like a problem with ( my understanding of ) complexity theory in general. Categorizing problems by "The size of the input" is too imprecise when irrational numbers are a part of the problem.
Why would it be too imprecise?
I agree there are some (many?) problems with some definitions used in complexity theory, but "size of input" is certainly not part of the problem. It can be defined very precisely. I don't see the slightest problem with how it's framed.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#13>> Suppose that I can find some lists of numbers whose sums of square roots are equal for the first ten million decimal points and then start being different
Would have been nice to add an example of such list in the blog, I wonder how short that list can be.
Also, how important is this in practice? The algorithms using this comparison could handle the 3 cases with a tolerance (larger, smaller, undecided)?
Re: A surprisingly hard CS problem: sums of square roots (2018)
#14> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this.
You can write down a completely explicit bound here using the Mahler-Mignotte root separation bound. More generally, for any algebraic expression involving algebraic numbers, you can bound a priori the number of digits you need to check to determine its sign.
When you involve transcendental numbers, things do get much harder though.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#15The part of this post that I find most wonderful/strange:
> EDIT: I think that Edward Kmett and Paul Crowley might have figured out how to solve this problem in the comments on my Facebook post; see here. I’ll investigate further and update.
> EDIT 2: actually we didn’t solve the problem, but it might still be a good direction for future research.
Possibly ground-breaking math being done on comments on a Facebook post.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#16Why would one try to formulate it as a function of the input length in binary? Does this have a practical relevance? Why not think about it in terms of the numbers given in decimal, their count and their size? And what is the input length in this problem? The numbers encoded in binary? Pretty sure it cannot be computed by just looking at how many numbers are given in each list.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#17It probably has been tried already by someone, but how about this: all square roots can be written as repeating continued fractions [1]. With a bit of work, continued fractions can also be summed [2] and compared. Wouldn't this take less than exponential time? [1] http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s... [2] https://www.jstor.org/stable/1969389
You're assuming that the period will remain of manageable size. I see no reason why this should be the case.
Edit: Also found a more accessible website describing how to do arithmetic with continued fractions: https://perl.plover.com/yak/cftalk/. In case anyone wants to try it out.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#18This looks more like a problem with ( my understanding of ) complexity theory in general. Categorizing problems by "The size of the input" is too imprecise when irrational numbers are a part of the problem.
Irrational numbers are involved in the problem, but not in the the size of the input, which is a list of natural numbers. There are a number of reasonable ways to encode such a list but they'll all scale in more or less the same way and be equivalent when looking at big O notation.
Re: A surprisingly hard CS problem: sums of square roots (2018)
#19This looks more like a problem with ( my understanding of ) complexity theory in general. Categorizing problems by "The size of the input" is too imprecise when irrational numbers are a part of the problem.
[deleted]
Re: A surprisingly hard CS problem: sums of square roots (2018)
#20This looks more like a problem with ( my understanding of ) complexity theory in general. Categorizing problems by "The size of the input" is too imprecise when irrational numbers are a part of the problem.
If you assume that mathematical notation (language) doesn't abstract complexity in a uniform fashion (something you can write and capture meaning with a few symbols isn't inherently more or less complex than something you can write with a lot of symbols), it becomes pretty obvious that something isn't necessarily as simple as it may look at the surface.
Having worked in computing for long enough, I'm well aware of this fact in the world of estimating time (which to some degree is estimating complexity) to address a given problem request. I can very easily write down in English a pretty generalized description that you need to: cure any and all forms of cancer. That's a fairly concise request, I can write it in one line, but it hides a mountain of complexity needed to accomplish that. It also doesn't describe what we consider as "cure" or "cancer" which can be ambiguous in some cases.
Much of the same is true with seemingly cute conjectures that seem to capture a behavior that may be incredibly complex to prove (if not impossible, e.g. Godel). The Collatz conjecture comes to mind where Paul Erdos famously said something to the effect of "Mathematics may not be ready for such problems."