Papex

Open problem · Computer science · Open

Square-root sum problem

Can a Turing machine decide in polynomial time whether a sum of square roots of integers is at most a given integer?

Summary

The problem is easy on an idealised real-number machine, but in the standard model the sum may need very many digits to compare. Exact answers to geometric problems such as the Euclidean travelling salesman depend on it.

Why it is open

Algorithms in computational geometry are often analysed on the real RAM, where real values are stored and compared in constant space and time [10]. On such machines the problem is easy: P. Tiwari showed in 1992 that it can be solved in polynomial time on a unit-cost arithmetic RAM by Newton iteration, and Nikhil Balaji and Samir Datta note that it has a polynomial-time algorithm on the real RAM [3, 7]. In the bit or Turing model, no subexponential-time algorithm is known [7].

The difficulty is precision. The best methods approximate the roots and rely on separation bounds, lower bounds on how small a nonzero sum can be [8, 11]. The Open Problems Project, a list of open problems in computational geometry, asks for tight bounds on r(n, k), the smallest positive value of |√a₁ + … + √a_k − √b₁ − … − √b_k| with all integers at most n [11]. If log(1/r(n, k)) is bounded by a polynomial in k and log n, the sign of such a sum can be computed in polynomial time; if not, a polynomial-time algorithm may still exist [11].

Michael Garey, Ronald Graham and David Johnson posed the question in 1976 in connection with the Euclidean travelling salesman problem [3, 7]. Their proofs indicate that it is NP-hard with Euclidean distances, but they questioned whether it, or even the minimum spanning tree problem, is then in NP [1]; NP is the class at the centre of P versus NP. David Eppstein, quoted by the Open Problems Project, calls the "mismatch between the real-number and Turing machine models of computation" a major bottleneck in proving NP-completeness for geometric problems [11].

A resolution would be a polynomial-time algorithm in the Turing model, as Wikipedia's list of unsolved problems in computer science asks [12], or evidence that none exists; Balaji and Datta note that no non-trivial lower bounds are known [7]. Exact equality is not the obstacle: Johannes Blömer gave a polynomial-time Monte Carlo algorithm that decides whether a sum of radicals is zero [2, 8].

What is known

Complexity bounds (1976–2023). Garey, Graham and Johnson credit Andrew Odlyzko with observing that approximating each root to O(k·2^k) bits suffices, which gives an exponential-time algorithm [7]. Modelling it in the existential theory of the reals places it in PSPACE, the class of problems solvable with polynomial memory [8]. In 2009 Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen showed that PosSLP lies in the counting hierarchy, specifically in P^(PP^(PP^PP)) [3]. PosSLP asks whether an arithmetic circuit with addition and multiplication gates, whose only input is −1, computes a positive integer [7]; the counting hierarchy is the sequence of classes PP, PP^PP and so on, and lies inside PSPACE [3]. Combining this with Tiwari's algorithm, they placed the square-root sum problem and the Euclidean travelling salesman problem in the counting hierarchy; for the latter, the previous best upper bound had been PSPACE [3]. In 2023 Balaji and Datta described this as the best known upper bound for the problem [7]. Allender and colleagues also showed that in the Blum–Shub–Smale model, which treats infinite-precision arithmetic as free, polynomial-time computation on discrete inputs with only algebraic constants is polynomial-time equivalent to PosSLP [3].

Where it appears. Geometric optimisation problems such as the Euclidean travelling salesman and Euclidean shortest path problems rely on comparing sums of square roots, for example the lengths of two polygonal paths [5, 8]. The Euclidean travelling salesman problem is not known to be in NP, but it is in NP relative to the square-root sum problem [3]. Kousha Etessami and Mihalis Yannakakis reduced the square-root sum problem to questions about termination probabilities of recursive Markov chains, a model of probabilistic programs with procedures, and concluded that their PSPACE bounds for those questions cannot be substantially improved without a breakthrough on it [4]. Balaji and Datta list further uses in algorithmic game theory, semidefinite programming and probabilistic verification [7].

How small a nonzero sum can be (1981–2024). Joseph O'Rourke posed the question about r(n, k) in 1981 [11]. Root-separation bounds, such as that of Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn and Stefan Schirra, give −log r(n, k) ≤ O(2^(2k) log n), so exponentially many bits always suffice [11]. In the other direction, Jianbo Qian and Cao An Wang showed that r(n, k) = O(n^(−2k+3/2)), which settles positively whether the number of bits needed can ever exceed the total number of bits in the input integers [11]. For sums E = x₁√a₁ + … + x_m√a_m with integer xᵢ, Friedrich Eisenbrand, Matthieu Haeberle and Neta Singer describe the best previous bound as doubly exponentially small and prove |E| ≥ γ·(m·max|xᵢ|)^(−2m) whenever E ≠ 0, where γ depends on the aᵢ and is not explicit [8]. For fixed aᵢ their bound is singly exponential in m, and its exponent of max|xᵢ| is asymptotically tight [8]. They add that there is no empirical evidence that 1/|E| can be doubly exponential in m, and that the best empirical lower bounds are of the form (max aᵢ)^Ω(n) [8]. Qi Cheng, Xianmeng Meng, Celi Sun and Jiazhe Chen related the minimum to short vectors in integer lattices; their lattice-reduction algorithm produces lower bounds "much better than the root separation technique does" [5].

Special cases. Neeraj Kayal and Chandan Saha settled the problem positively for integers that are values of suitable polynomials at a large number X [6]. Balaji and Datta showed that when the integers are at most k, so that they could be written in unary, the problem is in P/poly, solvable in polynomial time with advice of polynomial length that depends only on the input size [7]. One consequence is that this unary version cannot be NP-complete unless the polynomial hierarchy collapses to its second level [7].

Main approaches

Separation bounds. Show that a nonzero sum cannot be very small, then compute enough digits [8]. Strongest evidence: general root-separation bounds that are implemented for exact geometric computation [11], and the singly exponential bound for fixed aᵢ [8]. Main difficulty: the sum of the square roots of k distinct primes has a minimal polynomial of degree exactly 2^k, so, Balaji and Datta argue, this line of attack has limitations and "fundamentally new techniques" are needed to improve the complexity substantially [7]; the new bound's constant is not explicit [8].

Geometry of numbers. Translate small sums into short vectors in lattices [5, 8]. Strongest evidence: lattice-reduction lower bounds that beat root separation in computations, and the subspace-theorem bound [5, 8]. Main difficulty: Cheng and colleagues can prove only an exponential-time bound for their algorithm; polynomial time depends on their conjecture about shortest vectors, formulated from numerical data [5].

Complexity classes. Reduce the problem to PosSLP and place PosSLP among classical classes [3]. Strongest evidence: membership in the counting hierarchy [3]. Main difficulty: Allender and colleagues leave better upper bounds for PosSLP, and any hardness result for it, as major open problems [3].

Restricted inputs. Solve families of instances with extra structure [6, 7]. Strongest evidence: the P/poly bound for unary inputs, which its authors call a strong indication that this version is in P [7]. Main difficulty: the bound is non-uniform [7], and Kayal and Saha's result needs X larger than (B + 1)(k·d)^O(1), where k is the number of terms, B bounds the polynomials' coefficients and d their degrees [6].

Open sub-questions

  1. An explicit constant. Can the constant γ in the bound of Eisenbrand, Haeberle and Singer be made explicit, for example through explicit bounds on the number of solutions in the subspace theorem, which they pose as an open problem [8]?
  2. The lattice conjecture. Is the conjecture of Cheng and colleagues on the length of the shortest nonzero vector in their lattices true? It would make comparing sums of square roots of small integers polynomial-time [5].
  3. Unary inputs in P. Can the advice in Balaji and Datta's P/poly algorithm be computed in polynomial time, which would place the unary version in P [7]?
  4. Any hardness. Is there a polynomial-time reduction from a problem believed to be intractable to the square-root sum problem or to PosSLP [3, 7]?
  5. Near-integers. For k ≥ 3, how fast does the smallest nonzero distance from √a₁ + … + √a_k to an integer shrink with n, for integers up to n? Dana Angluin and Sarah Eisenstat found order n^(−3/2) for k = 2, and Stefan Steinerberger's construction gives at most c_k·n^(−c·k^(1/3)) for every k ≥ 2 [9, 11].

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Garey, M. R., Graham, R. L. & Johnson, D. S. (1976). Some NP-complete geometric problems. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing (STOC 1976), 10–22. 10.1145/800113.803626 · Checked 16 Oct 2026
  2. Blömer, J. (1991). Computing sums of radicals in polynomial time. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), 670–677. 10.1109/SFCS.1991.185434 · Checked 16 Oct 2026
  3. Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J. & Miltersen, P. B. (2009). On the complexity of numerical analysis. SIAM Journal on Computing 38(5), 1987–2006. 10.1137/070697926 · Checked 16 Oct 2026
  4. Etessami, K. & Yannakakis, M. (2009). Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM 56(1), 1–66. 10.1145/1462153.1462154 · Checked 16 Oct 2026
  5. Cheng, Q., Meng, X., Sun, C. & Chen, J. (2010). Bounding the sum of square roots via lattice reduction. Mathematics of Computation 79(270), 1109–1122 (published online 2009). 10.1090/S0025-5718-09-02304-7 · Checked 16 Oct 2026
  6. Kayal, N. & Saha, C. (2012). On the sum of square roots of polynomials and related problems. ACM Transactions on Computation Theory 4(4), 1–15. 10.1145/2382559.2382560 · Checked 16 Oct 2026
  7. Balaji, N. & Datta, S. (2024). USSR is in P/poly. In 2024 Symposium on Simplicity in Algorithms (SOSA), 151–159. 10.1137/1.9781611977936.15 · Checked 16 Oct 2026
  8. Eisenbrand, F., Haeberle, M. & Singer, N. (2024). An improved bound on sums of square roots via the subspace theorem. In 40th International Symposium on Computational Geometry (SoCG 2024), LIPIcs 293, 54:1–54:8. 10.4230/LIPIcs.SoCG.2024.54 · Checked 16 Oct 2026
  9. Steinerberger, S. (2024). Sums of square roots that are close to an integer. Journal of Number Theory 262, 45–57. 10.1016/j.jnt.2024.03.002 · Checked 16 Oct 2026
  10. Erickson, J., van der Hoog, I. & Miltzow, T. (2024). Smoothing the gap between NP and ER. SIAM Journal on Computing 53(6), FOCS20-102–FOCS20-138 (published online 2022); conference version in FOCS 2020. 10.1137/20M1385287 · Checked 16 Oct 2026
  11. Demaine, E. D., Mitchell, J. S. B. & O'Rourke, J. (eds.). Problem 33: Sum of square roots. The Open Problems Project; entry by E. Demaine, J. O'Rourke and J. Mitchell, last revised 9 September 2009. Source · Checked 16 Oct 2026
  12. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing