Is the square-root sum problem convex?

Question

The square-root sum problem is: given positive integers $a_1,\ldots,a_k$ and $b_1,\ldots,b_k$, decide if $\sum_i \sqrt{a_i} > \sum_i \sqrt{b_i}$. The exact run-time complexity of this problem is an open problem, as far as I know.

Can this problem be solved approximately using convex programming? I thought of the following formulation:

$$ \text{maximize } \sum_i x_i - \sum_i y_i $$

$$ \text{subject to } x_i^2 -a_i \leq 0 \text{ and } y_i^2 - b_i \geq 0. $$ If the optimal value is positive then the answer is "yes", otherwise the answer is "no".

But there is a problem: the constraint $y_i^2-b_i\geq 0$ is not convex.

Is there another way to solve the problem using convex programming?

Answer 1

The problem is not where you think it is.

To decide this, you would normally just add up the square roots and compare the sums. The problem arises when both sums are close together, so you cannot easily prove which sum is larger. Now consider that all we know is that the numbers are integers. They could be 100 digit integers, and with some effort one could find two sets that produce sums equal to 100s of digits.

So the problem is that we cannot find upper limits for the precision needed to decide which sum is larger.