Square-root sum problem

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

Details

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$.

The problem 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 1999. 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

The square-root sum problem 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.