The square-root sum problem (SRS) is a computational decision problem from the field of numerical analysis, with applications to computational geometry.
SRS is defined as follows:[1]Given positive integers
.An alternative definition is:Given positive integers
.The problem was posed in 1981,[2] and likely earlier.
SRS can be solved in polynomial time in the Real RAM model.
[3] However, its run-time complexity in the Turing machine model is open, as of 1997.
[1] 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.
The problem is mentioned in the Open Problems Garden.
[4] Blomer[5] presents a polynomial-time Monte Carlo algorithm for deciding whether a sum of square roots equals zero.
The algorithm applies more generally, to any sum of radicals.
Allender, Burgisser, Pedersen and Miltersen[6] prove that SRS lies in the counting hierarchy (which is contained in PSPACE).
One way to solve SRS is to prove a lower bound on the absolute difference
Such lower bound is called a "separation bound" since it separates between the difference and 0.
For example, if the absolute difference is at least 2−d, it means that we can round all numbers to d bits of accuracy, and solve SRS in time polynomial in d. This leads to the mathematical problem of proving bounds on this difference.
Define r(n,k) as the smallest positive value of the difference
, where ai and bi are integers between 1 and n; define R(n,k) is defined as -log r(n,k), which is the number of accuracy digits required to solve SRS.
Computing r(n,k) is open problem 33 in the open problem project.
[7] In particular, it is interesting whether r(n,k) is in O(poly(k,log(n)).
A positive answer would imply that SRS can be solved in polynomial time in the Turing Machine model.
Some currently known bounds are: SRS is important in computational geometry, as Euclidean distances are given by square-roots, and many geometric problems (e.g.
Minimum spanning tree in the plane and Euclidean traveling salesman problem) require to compute sums of distances.
Etessami and Yannakakis[13] show a reduction from SRS to the problem of termination of recursive concurrent stochastic games.
SRS also has a theoretic importance, as it is a simple special case of a semidefinite programming feasibility problem.
This matrix is positive semidefinite iff
Therefore, to solve SRS, we can construct a feasibility problem with n constraints of the form
, and additional linear constraints
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).
Kayal and Saha[14] extend the problem from integers to polynomials.
Their results imply a solution to SRS for a special class of integers.