I recently learned a wonderfully mind-blowing computer science fact from Peter Schmidt-Nielsen:
Consider the following problem: Given two sequences of natural numbers, compute the sums of the square roots of the respective lists, and then return which of the sums was larger. So if your lists were [1,4] and [9,9], you’d get 1 + 2 compared to 3 + 3, and you’d say that the second was larger.
How quickly can we compute this, as a function of the length of the input encoded in binary? You might enjoy taking a second to think about this.
. . . . .
The best known algorithm for this problem is in PSPACE. That is, it takes exponential time but only polynomial space. That means that as far as we know, this problem is crazily hard—among other things, PSPACE is harder than NP.
When I first heard this claim, I thought it was unbelievable. After all, isn’t there an obvious algorithm that works? Namely, in Haskell:
sumOfSqrts xs ys = sum (map sqrt xs) < sum (map sqrt ys)
And that looks to me like it takes linear time.
But it doesn’t work. The problem is that this algorithm is assuming finite precision, which isn’t necessarily enough to answer this question. 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. If we run my Haskell algorithm, we’ll erroneously be told that the sums are equal when actually they’re not. So we need to do something smarter.
The correct algorithm acknowledges that square roots (and therefore sums of square roots) aren’t finite precision numbers, they’re infinite streams of decimals. So it tells us to we take our two lists and start iteratively computing more and more digits of their sums-of-square-roots until we find a place where they disagree. And then we’re done. (If the sums of square roots are equal, this algorithm of course won’t halt. There’s a known, reasonably fast algorithm (in BPP) for checking equality of sums of square roots, so we shouldn’t worry about that too much.)
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.
This comes down to “are you able to embed complicated relationships inside of sums of square roots”. Like, we’re basically asking whether you can construct lists with absurdly close sums of square roots. This feels to me like a pretty deep question about square roots. There are other domains where this problem is obviously hard and obviously easy. For example, suppose you want to know whether two programs encode the same bit string, and all you can do is run them a step at a time and see what they output. It’s really easy for me to construct short programs that take an extremely long time before they disagree: for example “always print 0” and “output Graham’s number of zeros, then ones”. 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.
My guess is that this problem is actually in P, and we’re just stuck on proving it because irrational numbers are confusing and hard to prove things about, and most of the people who would be good at working on this are doing something more useful instead.
But if it turns out that I’m wrong, and that sums of square roots can get very close indeed, I’m going to update towards thinking that integers and square roots are much scarier, richer objects than I’d thought. I’ve updated to being more scared of real numbers than I used to be—they have all these sketchy properties like “almost none of them have finite descriptions”. Real numbers, and sets, and logical statements, have all started feeling to me like Cthuluesque monstrosities whose appearances are only tolerable because we only look at the pretty parts of them and don’t let ourselves look at the horrors that lurk below.
Incidentally, 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.
—
Like all great mind-blowing facts, this one sounded initially preposterous and then after a few minutes seemed completely obvious. I love it.
To read more about this, see here.
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.
See Facebook comments here