Square-root sum problem

The square-root sum problem (SRS) is a computational problem from the field of numerical analysis.

Details

SRS is a decision problem. It is defined as follows:

Given n positive integers $a_{1},\ldots ,a_{n}$ and an integer k, decide whether $\sum _{i=1}^{n}{\sqrt {a_{i}}}\leq k$.

An alternative definition is:

Given 2n positive integers $a_{1},\ldots ,a_{n}$ and $b_{1},\ldots ,b_{n}$, decide whether $\sum _{i=1}^{n}{\sqrt {a_{i}}}\leq \sum _{i=1}^{n}{\sqrt {b_{i}}}$.

SRS can be solved in polynomial time in the Real RAM model. However, its run-time complexity in the Turing machine model is open, as of 1997. The main difficulty is that, in order to solve the problem, the square-roots should be computed to a high accuracy, which may require a large number of bits.

Importance

SRS is important in computational geometry, as Euclidean distances are given by square-roots, and many geometric problems (e.g. Minimum spanning tree in geometry) require to compute sums of distances.

SRS also has a theoretic importance, as it is a simple special case of a semidefinite programming feasibility problem. Conisder the matrix $\left({\begin{matrix}1&x\\x&a\end{matrix}}\right)$. This matrix is positive semidefinite iff $a-x^{2}\geq 0$, iff $|x|\leq {\sqrt {a}}$. Therefore, to solve SRS, we can construct a feasibility problem with n constraints of the form $\left({\begin{matrix}1&x_{i}\\x_{i}&a_{i}\end{matrix}}\right)\succeq 0$, and additional linear constraints $x_{i}\geq 0,\sum _{i=1}^{n}x_{i}\geq k$. The resulting SDP is feasible if and only if SRS is feasible. As the runtime complexity of SRS in the Turing machine model is open, the same is true for SDP feasibility (as of 1997).