Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A surprisingly hard CS problem: sums of square roots (2018)

shlegeris.com

Post reply on HN
Print view View original

41–50 of 189 posts

Re: A surprisingly hard CS problem: sums of square roots (2018)

#41

Post by blackbear_ »

ogogmad wrote: post #29
blackbear_ wrote: post #27

Doesn't this imply that every algorithm that compares real numbers is in PSPACE?

The predicates are strictly semidecidable, meaning that if two real numbers are equal to each other, then no algorithm is guaranteed to terminate. The complexity is thus RE, which is worse than PSPACE. But the real numbers which show up in the sum-of-square-roots problem are from being as general as possible, so the complexity is PSPACE at worst. The foundations needed to understand general real number computation ar…

Super interesting, thanks a lot fot the resources!

Re: A surprisingly hard CS problem: sums of square roots (2018)

#42

Post by pfortuny »

syki wrote: post #40
pfortuny wrote: post #34

Earlier quoted context omitted.

Exactly: algebraic numbers, despite not being periodic, are in general "reasonably far from each other", and especially from rationals. I guess the problem can be solved using what you say, certainly. It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).

Rational numbers are algebraic so how are algebraic numbers reasonably far from each other? Algebraic numbers are dense in the real number line.

It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental.

https://mathworld.wolfram.com/LiouvillesApproximationTheorem...

My statement above may be a bit confusing, though.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#43

Post by probably_wrong »

mabbo wrote: post #15

The 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 pos…

Just wait until you hear about the paper [1] inspired by a Twitter discussion that ended up winning the "Best theme paper" award in the ACL Conference 2020.

[1] Climbing towards NLU: On Meaning, Form, and Understanding in the Age of Data: https://aclanthology.org/2020.acl-main.463.pdf

Re: A surprisingly hard CS problem: sums of square roots (2018)

#44

Post by umvi »

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.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#45

Post by zelphirkalt »

ufo wrote: post #38
zelphirkalt wrote: post #16

Why 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.

Input length in binary is the standard way to calculate computational complexity. Sometimes we handwave that away, but in problems like this where the size of the number matters, we stick to the more strict definition of computational complexity. Number in binary vs number in decimal doesn't make a big difference because it's just a constant factor.

Thanks really. I guessed as much. What about the other questions? How do you get to an input length from a list of numbers? Just concattenate all their binary digits? Can you answer any of these?

Re: A surprisingly hard CS problem: sums of square roots (2018)

#46

Post by fbanon »

mabbo wrote: post #15

The 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 pos…

*yawn* https://www.theverge.com/2018/10/24/18019464/4chan-anon-anim...

Re: A surprisingly hard CS problem: sums of square roots (2018)

#47

Post by ismayilzadan »

umvi wrote: post #44

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.

If question asked for just returning the sum, then yea, that would be acceptable. However, the question requires the comparison of sums. To decide which one is actually larger, 5-6 digits is not enough, even "practically".

Re: A surprisingly hard CS problem: sums of square roots (2018)

#48

Post by [deleted] »

fdej wrote: post #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 c…

[deleted]

Re: A surprisingly hard CS problem: sums of square roots (2018)

#49

Post by abetusk »

fdej wrote: post #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 c…

So, to state explicitly, given a list of positive integers, a_i, and coefficients, d_i \in {-1,1}, test whether \sum_i d_i sqrt(a_i) I guess there's different levels of bounds you can use (Mahler, Mahler-Mignotte, Davenporte-Mahler-Mignotte [0]) but they all involve the discriminant, the deg to the deg power (n^n) and maybe some other factors which put it neatly in a polynomial time bit representation. One bound puts it in the 2^{-2s^2} range, for bit size s [1].

Why does this not solve it? The problem as stated on cstheory.stackexchange explicitly says the square roots are square roots of integers [2]. What am I missing?

[0] https://arxiv.org/pdf/2005.07843.pdf

[1] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... (pg 165, Lecture VI, Section 7, Root separation (pdf pg. 197))

[2] https://cstheory.stackexchange.com/questions/79/problems-bet...

EDIT: I forgot to include the sqrt in the sum equation

Re: A surprisingly hard CS problem: sums of square roots (2018)

#50

Post by syki »

pfortuny wrote: post #42
syki wrote: post #40

Earlier quoted context omitted.

Rational numbers are algebraic so how are algebraic numbers reasonably far from each other? Algebraic numbers are dense in the real number line.

It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental. https://mathworld.wolfram.com/LiouvillesApproximationTheorem... My statement above may be a bit confusing, though.

They are using a different notion of “measure” than the standard notion of absolute value of the difference. Under the standard measure every number is within epsilon distance of a rational for any positive epsilon. Thank you for the clarification.
Post reply on HN