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

21–30 of 189 posts

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

#21

Post by dmurray »

erwincoumans wrote: post #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)?

I expect not very important in practice, because

1. We've settled on using IEEE 754 floating point numbers, and all their tolerance quirks, in practice, and still the bridges don't fall down

2. The author describes it as a little-studied field where "most of the people who would be good at working on this are doing something more useful instead"

But still, useless pure-maths distractions have a way of yielding results in unexpected fields. Maybe, as the author hints, a solution to this problem would bring us some information-theory insights and some new methods for cryptography or compression or whatever else.

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

#22

Post by dooglius »

qsort wrote: post #12
athrowaway3z wrote: post #7

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

So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?

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

#23

Post by [deleted] »

dooglius wrote: post #22
qsort wrote: post #12

Earlier quoted context omitted.

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.

So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?

[deleted]

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

#24

Post by jerf »

athrowaway3z wrote: post #7

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

I would say that imprecision is somewhat artificially induced by the fact we so thoroughly use IEEE floats that we tend to assume that they are the only numbers.

When invoking arbitrary-precision floats (or equivalent), pretty much all numerical calculations get a lot harder than we intuit instantly. So much as comparing one number to another without taking a square root goes from O(1) to O(n) for n = the representation of the shortest of the two numbers. Our IEEE-based intuition sees that and goes wha?

But you can also build a separate intuition based on the arbitrary representation that would make this easy to both understand and intuit. It's really easy to get into PSPACE with arbitrary precision. Heck, it's pretty easy to get into EXPSPACE and almost any other prefix to "SPACE" you want, because it's easy to stipulate very close numbers and transforms on those very close numbers that require obscene precision to be sure you're correct.

If you work in this sort of mind space all the time, it's perfectly precise to talk about arbitrary-precision numbers.

But the real universe we live in bottoms out at 10^-35 meters or so, our practical ability to be precise a dozen or two orders of magnitude sooner than that at a minimum (and often another dozen for macroscopic work), and the practical impact of this is minimal because in practice, the first Haskell solution in that post is essentially correct in our real universe 99.9% of the time, even though it is glaringly wrong mathematically, because in the real universe we never have hundreds of digits of precision, and that's where our intuition is built.

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

#25

Post by qsort »

dooglius wrote: post #22
qsort wrote: post #12

Earlier quoted context omitted.

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.

So what is N here? The sequence length, number of digits across all sequence elements, sum of all elements?

N is the sum of the lengths of the elements of all lists, when all elements are written in binary (or any other base, which is the same up to a constant).

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

#26

Post by dooglius »

edflsafoiewq wrote: post #11

> There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots What is it?

You just have to take out square factors from each, and combine terms with matching sqrt(n), and that will be unique

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

#28

Post by heavenlyblue »

athrowaway3z wrote: post #7

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

Have you read the article?

The author explicitly defines what the question is (and how the question of irratonality of numbers is resolved there).

As a matter of fact they explicitly mention that the algorithm in question only requires polynomial memory space to compare N sums of roots of arbitrary numbers.

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

#29

Post by ogogmad »

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 are listed here: https://news.ycombinator.com/item?id=30057794

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

#30

Post by yalogin »

What does “ compute this as a function of the length of the input encoded in binary” mean? Can someone explain it with the other sample used in the article? Does it mean the input will be provided in binary form instead of decimal? How does that change things?
Post reply on HN