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

Re:A surprisingly hard CS problem: sums of square roots (2018) by umvi on Monday January 24, 2022 @10:36AM (#30058900)

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.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by ismayilzadan on Monday January 24, 2022 @10:47AM (#30059068)

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

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by parhamn on Monday January 24, 2022 @11:26AM (#30059767)

It's not really different. If you were given the sums in the first operation to 5-6 digits and it was acceptable error margin, the comparison is within that acceptable error margin too, it's just this time the error led to a wrong binary not a wrong decimal.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by bshlgrs on Monday January 24, 2022 @06:59PM (#30065936)

(Author here) As far as I know, there are no cases where this actually matters.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by tgflynn on Tuesday January 25, 2022 @09:40AM (#30072251)

In your post you say that a PSPACE algorithm exists. Do you have a reference for that algorithm ?

Another commenter here is saying the problem has an explicit exponential or worse lower bound.

If both of those claims are true that would prove P != PSPACE, which would be a very important result.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by ravi-delia on Monday January 24, 2022 @02:08PM (#30062372)

I think that's basically fair. If we were dealing with the reals I'd assume that there was some uncountable number of pathological examples that just happen to exclude all the numbers we really care about (since God ran out of good numbers and had to scrape the bottom of the barrel to fill in the gaps), but the integers seem safe.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by mcherm on Monday January 24, 2022 @03:40PM (#30063706)

I have an very efficient and "practical" algorithm for determining the score in a sports match. In almost all cases it tells us which team had the higher score -- the only time it fails is when the game in close. In those cases, it can't accurately tell who won.

It SOUNDS like a very practical algorithm, but in reality it's precisely in the "close" cases where people care the most.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by whoomp12342 on Monday January 24, 2022 @11:55AM (#30060292)

we are talking about math here, there are always applications even ones where we dont know in this day and age.

I am positive the same question could be been asked about basic calculus concepts in the 12th century.

[ Parent | on HN ]

Re:A surprisingly hard CS problem: sums of square roots (2018) by umvi on Monday January 24, 2022 @12:10PM (#30060558)

Yeah, I get that, but I'm just saying if this is a problem needing solved to accomplish some visual effect in game programming (as a contrived example), that practically speaking it's not a hard problem. It's only a hard problem in a theoretical, general sense.

[ Parent | on HN ]