Square-root sum problem

Unsolved problem in computer science:

What is the Turing run-time complexity of the square-root sum problem?

(more unsolved problems in computer science)

The square-root sum problem (SRS) is a computational decision problem from the field of numerical analysis, with applications to computational geometry.

Definitions

SRS is defined as follows: ^[1]

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

An alternative definition is:

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

The problem was posed in 1981, ^[2] and likely earlier.

Run-time complexity

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

Allender, Burgisser, Pedersen and Miltersen ^[6] prove that SRS lies in the counting hierarchy (which is contained in PSPACE).

Separation bounds

One way to solve SRS is to prove a lower bound on the absolute difference ${\displaystyle \left|t-\sum _{i=1}^{k}{\sqrt {a_{i}}}\right|}$ or ${\displaystyle \left|\sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}\right|}$. 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 ${\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}}$, where a_i and b_i 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:

• Qian and Wang ^[8] prove by an explicit construction that, for any k and n, ${\displaystyle r(n,k)\in O(n^{-2k+3/2})}$, so ${\displaystyle R(n,k)\geq (2k-3/2)\cdot \log {n}}$. This number is optimal for k=2, and also for a wide range of integers.
• Burnikel, Fleischer, Mehlhorn and Schirra ^[9] proved an upper bound on the number of digits: ${\displaystyle R(n,k)\in O(2^{2k}\cdot \log {n})}$.
• Cheng, Meng, Sun and Chen ^[10] showed that ${\displaystyle R(n,k)\in 2^{O(n/\log {n})}\cdot \log {n}}$.
• Cheng and Li ^[11] showed that ${\displaystyle R(n,k)\in 2^{O(n/\log {n})}}$. This implies an that SRS can be solved in time ${\displaystyle 2^{o(k)}\cdot (\log {n})^{O(1)}}$, as long as n is in o(k log k). They also present an algorithm to compute r(n,k) in time ${\displaystyle n^{k+o(k)}}$.
• Eisenbrand, Haeberle and Singer ^[12] prove that ${\displaystyle r(n,k)\geq \gamma \cdot n^{-2n}}$, where gamma is a constant that depends on the inputs a₁,...,a_n, and steps from the Subspace theorem. This improves the previous bound ${\displaystyle r(n,k)\geq \left(n\cdot \max _{i}({\sqrt {a_{i}}})\right)^{-2^{n}}}$.

Applications

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.

Relation to semidefinite programming

SRS also has a theoretic importance, as it is a simple special case of a semidefinite programming feasibility problem. Consider the matrix ${\displaystyle \left({\begin{matrix}1&x\\x&a\end{matrix}}\right)}$. This matrix is positive semidefinite iff ${\displaystyle a-x^{2}\geq 0}$, iff ${\displaystyle |x|\leq {\sqrt {a}}}$. Therefore, to solve SRS, we can construct a feasibility problem with n constraints of the form ${\displaystyle \left({\begin{matrix}1&x_{i}\\x_{i}&a_{i}\end{matrix}}\right)\succeq 0}$, and additional linear constraints ${\displaystyle 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).

Extensions

Kayal and Saha ^[14] extend the problem from integers to polynomials. Their results imply a solution to SRS for a special class of integers.

References

1. Goemans, Michel X. (1997-10-01). "Semidefinite programming in combinatorial optimization". Mathematical Programming. 79 (1): 143–161. doi:10.1007/BF02614315. ISSN   1436-4646. S2CID   17221714.
2. O’Rourke, Joseph (1981). "Advanced problem 6369". Amer. Math. Monthly. 88 (10): 769.
3. Tiwari, Prasoon (1992-12-01). "A problem that is easier to solve on the unit-cost algebraic RAM". Journal of Complexity. 8 (4): 393–397. doi:10.1016/0885-064X(92)90003-T. ISSN   0885-064X.
4. "Complexity of square-root sum | Open Problem Garden". garden.irmacs.sfu.ca. Retrieved 2024-01-01.
5. "CSDL | IEEE Computer Society". www.computer.org. Retrieved 2024-01-01.
6. Allender, Eric; Bürgisser, Peter; Kjeldgaard-Pedersen, Johan; Miltersen, Peter Bro (January 2009). "On the Complexity of Numerical Analysis". SIAM Journal on Computing. 38 (5): 1987–2006. doi:10.1137/070697926. ISSN   0097-5397.
7. Demaine, Erik D.; Mitchell, Joseph; O'Rourke, Joseph. "TOPP: Problem 33: Sum of Square Roots". topp.openproblem.net. Retrieved 2024-01-01.
8. Qian, Jianbo; Wang, Cao An (2006-12-16). "How much precision is needed to compare two sums of square roots of integers?". Information Processing Letters. 100 (5): 194–198. doi:10.1016/j.ipl.2006.05.002. ISSN   0020-0190.
9. Burnikel, C.; Fleischer, R.; Mehlhorn, K.; Schirra, S. (2000-05-01). "A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals". Algorithmica. 27 (1): 87–99. doi:10.1007/s004530010005. ISSN   1432-0541. S2CID   34502818.
10. Cheng, Qi; Meng, Xianmeng; Sun, Celi; Chen, Jiazhe (April 2010). "Bounding the sum of square roots via lattice reduction". Mathematics of Computation. 79 (270): 1109–1122. arXiv: 0905.4487 . Bibcode:2010MaCom..79.1109C. doi: 10.1090/S0025-5718-09-02304-7 . ISSN   0025-5718.
11. Cheng, Qi; Li, Yu-Hsin (2011-09-09). "On the minimum gap between sums of square roots of small integers". Theoretical Computer Science. 412 (39): 5458–5465. doi: 10.1016/j.tcs.2011.06.014 . ISSN   0304-3975.
12. Eisenbrand, Friedrich; Haeberle, Matthieu; Singer, Neta (2023). "An improved bound on sums of square roots via the subspace theorem". arXiv: 2312.02057 [cs.CG].
13. Etessami, Kousha; Yannakakis, Mihalis (2008-11-11). "Recursive Concurrent Stochastic Games". Logical Methods in Computer Science. 4 (4). arXiv: 0810.3581 . doi: 10.2168/LMCS-4(4:7)2008 . ISSN   1860-5974.
14. Kayal, Neeraj; Saha, Chandan (2012-11-01). "On the Sum of Square Roots of Polynomials and Related Problems". ACM Transactions on Computation Theory. 4 (4): 9:1–9:15. doi:10.1145/2382559.2382560. ISSN   1942-3454. S2CID   7225729.

^[1]

1. O'Rourke, Joseph (1981). "Advanced problem 6369". Amer. Math. Monthly. 88 (10): 769.