Sum of Radicals

(You can watch the video version of this post on YouTube.)

We’ve talked about “reasonable encodings” of integers, and why that matters, but what about real numbers? You could give a finite expansion, that’s fine, or use rational numbers - though in either case you might have to be a little bit careful about how large your representation is and, uh, if you can actually work with that representation efficiently.

SUM (REALS)
INPUT: two sets of numbers $A,B\in\mathbb{R}^n$
PROPERTY: $\displaystyle\sum_{a\in A} a \leq \sum_{b\in B}b$

That seems .. easy enough, right? This is clearly easy on a real RAM machine, or on a Turing machine if these are all integers.

SUM (INTEGERS)
INPUT: two sets of numbers $A,B\in\mathbb{Z}^n$
PROPERTY: $\displaystyle\sum_{a\in A} a \leq \sum_{b\in B}b$

But what if I have .. let’s say, a bunch of square roots in there? How about THIS problem: given two sets of integers, represented reasonably, is the sum of square roots of the one larger than the sum of the square roots of the other?

SUM (SQUARE ROOTS)
INPUT: two sets of numbers $A,B\in\mathbb{N}^n$
PROPERTY: $\displaystyle\sum_{a\in A} \sqrt{a} \leq \sum_{b\in B}\sqrt{b}$

At time of writing, I don’t think that we have an algorithm for this that we know runs in worst-case polynomial time. There are a bunch of things that you can do – look them up if you need to, this is a version of the SUM OF RADICALS problem – but the very short version of what the difficulty could even be, is that, well, sums of square roots don’t really simplify the way you would want, and we don’t know that working up to some polynomial finite precision is enough to tell the difference between these sums. Could be a tiny difference.

$$\sqrt{28} + \sqrt{82} = \mathbf{14.346887}7602665\ldots$$ $$\sqrt{33} + \sqrt{74} = \mathbf{14.346887}913580\ldots$$

So watch out with irrational numbers in your instances, I guess, and I think we’ll talk about this some more in the future.