Square-Root Sum Problem

The exact decision problem of comparing a binary-encoded sum of square roots of positive integers with an integer or competing radical sum, whose unresolved bit complexity turns nonzero separation from zero into the central computational resource.

Version

v3 · 2026-09-06 · History

Domain-specific #

2835

Origin domain

theoretical computer science

Subdomain

exact numerical computation

Core Idea

The Square-Root Sum Problem asks for an exact Boolean comparison of succinctly represented irrational quantities. In its threshold form, the input is a finite list of positive integers \(a_1,\ldots,a_k\) and an integer \(t\), ordinarily encoded in binary, and the output is whether

\[ \sum_{i=1}^{k}\sqrt{a_i}\leq t. \]

An equivalent comparison form asks whether \(\sum_i\sqrt{a_i}\leq\sum_j\sqrt{b_j}\). Moving all terms to one side gives the standard signed form: determine the sign of

\[ E=\sum_{i=1}^{m}\delta_i\sqrt{c_i},\qquad \delta_i\in\{-1,+1\}. \]

An integer threshold can be represented as \(\sqrt{t^2}\) with the appropriate sign. Repeated terms allow integer coefficients, although a formulation that supplies large coefficients directly in binary is a more succinct generalized input and must not automatically inherit every bound for the unit-coefficient problem.^[1][2][3]

The arithmetic expression is elementary; its exact bit complexity is not. A numerical algorithm can approximate each square root rapidly, but the comparison is certified only after its error interval lies wholly on one side of zero—or exact equality has been decided. If a nonzero \(E\) can be extraordinarily close to zero, many bits may be needed before the sign becomes visible. A separation bound gives a lower bound on \(|E|\) conditional on \(E\ne0\); its bit length becomes an upper bound on the precision needed for a certified sign decision.^[4][5]

This model-sensitive precision bottleneck is the abstraction's autonomous identity. On a unit-cost algebraic or real-RAM model that treats exact algebraic operations and comparisons as constant-cost primitives, the problem is polynomial-time solvable. On the ordinary Turing/bit model, the complexity of the binary-input problem remains open: work through 2025 still reports that it is not known to be in polynomial time or even in NP. A counting-hierarchy containment is known for the standard Square-Root Sum problem, and hence a PSPACE upper bound follows, but no comparable nontrivial lower-bound classification is known.^{[2][6][3][7][8]}

The node is therefore not “addition with radicals.” It is the recurring decision architecture succinct algebraic inputs → exact signed comparison → model-dependent certification via equality and separation.

Structural Signature

A qualifying Square-Root Sum instance preserves these roles:

1. Discrete radicand input. Positive integers are encoded finitely, normally in binary, and the number of terms is part of the input. Input encoding is load-bearing: unary radicands define a restricted variant.
2. A radical linear form. The compared quantity is a finite sum of square roots with unit signs, an integer threshold, or two positive sums moved to a signed difference.
3. An exact order predicate. The requested output is \(<\), \(\leq\), \(>\), or \(\geq\) for the exact real values—not an approximation within an unspecified tolerance.
4. An equality branch. A sound sign procedure must account for \(E=0\). Equality testing for sums of radicals is a related but easier problem with polynomial-time algorithms; it does not by itself decide which side of zero a nonzero expression lies.^[9][3]
5. A nonzero separation certificate. If \(E\ne0\), a bound \(|E|\geq 2^{-B}\) licenses evaluation to somewhat more than \(B\) bits, including accumulated-error guard bits, to determine the sign.
6. A computational model. Real-RAM and Turing-machine claims are distinct because exact real operations cost one step in the former while precision and integer bit lengths count in the latter.^[2]
7. A complexity status. The problem is easy to state but has an unresolved exact bit-complexity classification. Counting-hierarchy containment, special-input results, and separation bounds narrow the uncertainty without settling polynomial time or NP membership.^[6][3]
8. A reduction interface. Exact Euclidean length comparisons and several quantitative verification problems reduce to Square-Root Sum, so an improved algorithm or class containment propagates beyond radical arithmetic.^[1][10]

Recognition test. Ask whether the input is a finite integer description, the output is the exact sign/order of a sum of square roots, and precision is part of the bit-cost rather than a free primitive. If any of those is absent, the object is another problem.

What It Is Not

• Not evaluating one square root. Individual square roots can be approximated efficiently to any requested number of bits. The unresolved issue is how many bits the worst-case sign comparison requires as a function of the succinct input.
• Not the equality-only problem. Testing \(E=0\) is polynomial-time solvable by algebraic methods. Deciding the sign of a nonzero value adds the separation problem.^[9]
• Not sum-of-radicals simplification. Symbolically rewriting \(\sqrt8=2\sqrt2\) can solve easy instances, but no known simplification rule yields a polynomial-time sign algorithm for all binary inputs.
• Not a floating-point comparison with a chosen epsilon. Returning “equal” whenever \(|\widehat E|<10^{-12}\) changes the problem and can be wrong on closer nonzero inputs. A tolerance is sound only when tied to a proved error and separation bound.
• Not Root Sum or a root-of-polynomial problem. Those phrases can name sums of polynomial roots, symmetric functions of roots, or graph-square-root problems. Square-Root Sum fixes positive-integer radicands and an exact sign decision.
• Not the Sum of Two Squares theorem. That theorem characterizes integers representable as \(x^2+y^2\). It does not compare sums of irrational square roots.
• Not P versus NP. Square-Root Sum has an unresolved class placement, but it does not ask whether the classes P and NP coincide, nor is it known NP-hard or NP-complete.
• Not generic numerical conditioning. The issue resembles conditioning, but it is a precisely specified algebraic decision language with reductions and complexity-class bounds.
• Not the unary variant. Unary Square-Root Sum has a nonuniform \(P/poly\) upper bound; this does not establish a uniform polynomial-time algorithm for the binary problem.^[3]

Scope of Application

Square-Root Sum belongs to exact numerical computation, algebraic complexity, and computational geometry. Its canonical habitat is the comparison of Euclidean path lengths when coordinates are integers or rationals: a segment from \((x_1,y_1)\) to \((x_2,y_2)\) has length \(\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\), so a polygonal path or tour length is a sum of square roots of integers after clearing rational denominators. Comparing two tours or testing a length threshold can therefore require an SSR oracle.^[1][3][7]

This explains the problem's historical importance. Garey, Graham, and Johnson used exact Euclidean geometric problems to expose a gap between NP-hardness and demonstrated NP membership: a tour is a short combinatorial witness, but verifying its exact Euclidean length against a threshold requires the same radical comparison. Later counting-hierarchy work transferred a better upper bound to Euclidean TSP and related exact computations.^[1][6]

The reduction interface extends beyond geometry. Etessami and Yannakakis reduce Square-Root Sum to quantitative termination for finite concurrent stochastic games and onward to qualitative termination for recursive concurrent stochastic games. The point is not that those games contain literal geometric distances; their exact values encode radical comparisons. Such results use “Square-Root-Sum-hard” as a meaningful conditional barrier: improving the target problem to NP or P would also improve SSR.^[10]

Semidefinite feasibility provides another exact encoding. The \(2\times2\) matrix

\[ \begin{pmatrix}1&x_i\\x_i&a_i\end{pmatrix}\succeq0 \]

is equivalent to \(|x_i|\leq\sqrt{a_i}\). Adding \(x_i\geq0\) and \(\sum_i x_i\geq t\) makes feasibility equivalent to \(\sum_i\sqrt{a_i}\geq t\). The direction of the threshold matters, and approximation algorithms for SDP do not automatically settle exact feasibility at a boundary.^[11]

The scope excludes arbitrary algebraic-number comparison unless it reduces to this restricted radical form without exponential blowup. It also excludes practical geometric code that accepts filtered floating-point predicates plus a fallback exact method as a whole system; SSR is the exact predicate that may appear inside such a system.

Clarity

The abstraction clarifies three questions that are often conflated.

First, can the number be approximated? Yes: each \(\sqrt{a_i}\) can be computed to \(p\) bits in time polynomial in \(p\) and the input length. Second, does that approximation certify the requested sign? Only if the error interval excludes zero or equality has been established. Third, how large must \(p\) be in the worst case? That is the unresolved separation-and-complexity question. A fast approximation routine answers the first question, not the third.

The problem also forces model declarations. Saying “the problem is polynomial” without naming the model hides exactly what is difficult. A real-RAM may branch on an exact algebraic comparison in one step. A Turing machine must manipulate finite bit strings and pay for every precision bit. The former result shows that combinatorial search is not the obstacle; the gap between the models localizes the obstacle in exact algebraic sign determination.^[2]

A useful audit is: What is the exact signed expression? How are coefficients and radicands encoded? Is equality a permitted outcome? What interval contains the numerical error? What theorem separates a nonzero value from zero? Which computational model pays for those bits? If those questions are explicit, an algorithmic claim can be checked. If they are omitted, “we computed enough digits” is not a complexity proof.

Manages Complexity

Square-Root Sum compresses a broad family of exact numerical difficulties into one oracle problem. Rather than analyze every Euclidean optimization or stochastic-value comparison from scratch, a reduction isolates the hard predicate: if SSR can be solved within resource class \(C\), then the surrounding problem may inherit a \(C\)-relative algorithm; if the target is SSR-hard, improving it requires progress on the radical comparison. This standardizes what otherwise looks like unrelated numerical fragility.

Within an instance, interval refinement manages uncertainty. Approximate each radical with certified lower and upper bounds; add them with outward rounding; compare the resulting interval with the threshold. If the interval is separated from zero, terminate with a certified sign. If it straddles zero, increase precision or invoke symbolic equality/separation machinery. The method is correct for every terminating branch, but its worst-case complexity depends on how long a nonzero interval may continue to straddle zero.

Separation bounds convert algebraic structure into a resource budget. Burnikel and colleagues bound nonzero arithmetic expressions involving radicals by reasoning over algebraic conjugates. Qian and Wang construct close pairs showing that precision linear in the input digits times the number of terms can genuinely be necessary in fixed-\(k\) regimes. Eisenbrand, Haeberle, and Singer improve coefficient dependence for a generalized fixed-radicand setting using the subspace theorem, while explicitly noting that the resulting constant is ineffective and does not settle the uniform polynomial-time problem.^[4][5][7]

Special cases further map the frontier. Equality is polynomial-time decidable. Small/unary radicands admit a nonuniform \(P/poly\) upper bound and even stronger circuit bounds in the Balaji–Datta result. Certain bounded-radicand regimes have subexponential algorithms. These are genuine reductions in complexity, but they depend on input restrictions and cannot be generalized silently.^[9][3]

Abstract Reasoning

Square-Root Sum licenses a characteristic sequence of reasoning moves.

Normalize. Move all terms to one side, combine repeated radicands where possible, extract visible square factors, and record whether coefficients are unit-expanded or supplied succinctly in binary. This can collapse an easy instance without altering the formal problem.

Separate equality from order. Run or reason about exact zero testing independently. If \(E=0\), non-strict and strict predicates differ. If \(E\ne0\), the remaining task is a sign decision and a separation theorem may be applied. This explains why a polynomial equality algorithm does not solve SSR.

Certify by intervals. Compute enclosures \(L_i\leq\sqrt{a_i}\leq U_i\), propagate them with signs, and form \([L,U]\ni E\). If \(L>0\), certify positive; if \(U<0\), certify negative. If \(0\in[L,U]\), more precision or algebraic information is required. Ordinary floating-point values without directed error bounds cannot license the same inference.

Translate separation into time. If a theorem guarantees \(|E|\geq2^{-B}\) whenever \(E\ne0\), computing each radical with total accumulated error below \(2^{-B-1}\) suffices. Polynomial \(B\) in the bit input would imply a polynomial-time approximation-and-compare strategy. Exponential \(B\) yields only a correspondingly larger guarantee; it does not prove such precision is always necessary.

Track reductions. A Euclidean path with integer-coordinate segments yields an SSR expression; conversely, a reduction may encode SSR in game values or semidefinite constraints. The direction matters: SSR \(\leq_p X\) says an efficient algorithm for \(X\) would solve SSR, not that an SSR algorithm alone solves every aspect of \(X\).

Preserve status language. “Not known to be in NP” is an epistemic statement, not a separation theorem. “Contained in the counting hierarchy” is an upper bound, not completeness. “No subexponential algorithm is known” is not an exponential lower bound. The abstraction is especially useful because it forces these distinctions.

Knowledge Transfer

The full mechanism transfers literally wherever exact quantities reduce to a signed sum of square roots with polynomial-size discrete encoding. Integer-coordinate Euclidean tour comparison, polygonal-chain length comparison, some shortest-path predicates, and specific game or semidefinite-value encodings preserve the same radical expression, exact sign output, model distinction, and separation requirement.

A second exact transfer is methodological: filtered exact computation. A fast floating-point stage handles well-separated cases; an error bound decides whether the result is certified; ambiguous cases escalate to higher precision or symbolic algebra. That control flow occurs across robust computational geometry. It is not itself identical to SSR, but SSR supplies a canonical worst-case predicate explaining why the fallback may be hard.

Beyond exact numerical computation, talk of a “square-root-sum problem” is usually metaphor. Close election totals or nearly tied business metrics may require care, but they lack algebraic radicands, a Turing input encoding, counting-hierarchy placement, and conjugate-based separation. Their portable residue belongs to Comparison, Threshold, Error Bound, and Numerical Precision rather than this node.

Examples

Simplifiable yes-instance. Decide whether \(\sqrt2+\sqrt8\leq5\). Since \(\sqrt8=2\sqrt2\), the left side is \(3\sqrt2\). Both sides are nonnegative, so squaring gives \(18\leq25\); the answer is yes. The example is an SSR instance even though elementary normalization solves it.

Two-sum comparison. Decide whether \(\sqrt2+\sqrt3\leq\sqrt{10}\). Squaring the positive sides gives \(5+2\sqrt6\leq10\), equivalent to \(\sqrt6\leq5/2\), and squaring again gives \(6\leq25/4\). The comparison is true. Repeated squaring works here because signs remain controlled; indiscriminate squaring can introduce extraneous branches in larger expressions.

Equality boundary. \(\sqrt8-2\sqrt2=0\). A numerical routine may produce a tiny residual because the terms are rounded independently. Exact normalization detects equality, showing why a tolerance is not a definition and why non-strict versus strict comparison must retain an equality branch.

Euclidean path. An integer-coordinate path with displacement vectors \((1,1)\) and \((1,2)\) has length \(\sqrt2+\sqrt5\). Testing whether it is at most 4 is an SSR threshold instance. One exact derivation squares only positive quantities: \(\sqrt5<4-\sqrt2\) reduces to \(8\sqrt2<13\), then \(128<169\), so the path is shorter than 4.

Model contrast. A real-RAM program may form each radical and compare the exact sum in a polynomial number of unit-cost operations. A bit-model implementation that rounds each term must prove its interval excludes the threshold. The same syntax therefore has different certified cost under the two models.

Restricted input. If radicands are written in unary, their magnitudes are bounded by the input length. Balaji and Datta place that unary variant in \(P/poly\), a nonuniform circuit class. This is progress on a strict variant, not proof that binary SSR is in P.^[3]

Structural Tensions

• Simple expression versus unresolved classification. The input uses only integers, addition, signs, and square roots, yet its exact Turing complexity has resisted classification for decades.
• Fast approximation versus expensive certification. Computing more digits is routine; knowing how many digits suffice uniformly is the hard part.
• Real-RAM efficiency versus bit-model accountability. Treating exact real comparison as unit cost removes the very precision resource that dominates the discrete model.
• Equality tractability versus sign uncertainty. Exact zero testing is polynomial while determining the side of zero for a nonzero result remains open.
• Observed separation versus worst-case proof. Practical instances often separate quickly, but empirical comfort cannot replace a worst-case lower bound on nonzero magnitude.
• General upper bounds versus usable bounds. Algebraic-conjugate bounds guarantee termination but may demand exponentially many bits; stronger number-theoretic bounds may contain ineffective constants.
• Special-case progress versus general closure. Unary, bounded-radicand, or structured-coefficient results reveal mechanisms without automatically transferring to binary unrestricted inputs.
• Reduction usefulness versus hardness overstatement. SSR-hardness marks a conditional barrier even though SSR itself has no established NP-hardness or lower-bound classification.

Structural–Framed Character

Assessment: structural. The identity is determined by a formal input language, exact order predicate, computational model, error certificate, and reduction behavior. It does not depend on policy, social convention, evaluation, or institutional history. Independent implementations either return the correct algebraic sign or do not.

The abstraction is nevertheless domain-specific. Positive-integer radicands, binary encoding, Turing bit cost, real-RAM primitives, algebraic conjugates, counting-hierarchy notation, and polynomial reductions are constitutive. Strip them away and only the general act of comparing two quantities near a threshold remains.

Structural Core vs. Domain Accent

The portable core is bring two values into a common order relation, propagate certified error, and refine until their intervals separate from the decision boundary. This is recognizable as Comparison combined with Threshold, Error Bound, and Numerical Precision. It travels to many numerical predicates.

The domain accent makes the named problem: the values are sums of square roots of discrete positive integers; the exact output is a language decision; coefficients and radicands have a specified encoding; equality has specialized algebraic algorithms; separation can be bounded through conjugates and number theory; and complexity is measured in Turing or circuit classes. These details generate the unresolved status and the reductions to geometry and games.

The general skeleton is already covered by primes. The radical language and complexity consequences do not recur literally across unrelated substrates, so Square-Root Sum is retained as domain-specific rather than prime.

Instantiates / Related Primes

Proposed parent: prime:comparison. Every Square-Root Sum instance places two exact real quantities in the shared order of \(\mathbb R\) and asks which relation holds. The radical expression and bit-complexity difficulty specialize that universal comparison structure. The prospective edge is composition/instantiates/strict and proposal-only.

Related: prime:threshold. The integer-threshold form classifies a sum relative to a cutoff. The two-sum form needs no privileged threshold, so Threshold is not the sole universal parent.

Related: prime:error_bound and prime:numerical_precision. Certified intervals and separation bounds determine whether approximation licenses an exact decision. These are computational mechanisms, not exact coverage of the input language.

Related: domain_specific:complexity_class. Counting-hierarchy and PSPACE containments describe what resources are known to suffice. Square-Root Sum is one problem, not a complexity class.

Relationships to Other Abstractions

Current abstraction Square-Root Sum Problem Domain-specific

Parents (1) — more general patterns this builds on

• Square-Root Sum Problem is a kind of Comparison Prime

  Proposed parent: prime:comparison. Every Square-Root Sum instance places two exact real quantities in the shared order of \(\mathbb R\) and asks which relation holds.

Hierarchy path (1) — routes to 1 parentless root

• Square-Root Sum Problem → Comparison → Self Checking

Neighborhood in Abstraction Space

Square-Root Sum Problem sits in a sparse region of the domain-specific corpus (88^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• Euler's Four-Square Identity — 0.81
• Factorial Number System — 0.79
• Knuth–Eve Algorithm — 0.79
• Sum-Free Sequence — 0.79
• Primefree Sequence — 0.79

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

• P versus NP Problem (domain_specific:p_versus_np_problem). P versus NP asks whether two complexity classes coincide. SSR asks the sign of a radical sum and is not even known to lie in NP.
• Complexity Class (domain_specific:complexity_class). A class is a set of problems defined by resource bounds. SSR has upper-bound placements but is not itself a class.
• Comparison (prime:comparison). Comparison supplies the broad order relation. It does not supply radical inputs, exact-number separation, computational models, or open complexity status.
• Carlyle Circle. A Carlyle circle geometrically constructs roots of a quadratic polynomial. It neither compares radical sums nor expresses their bit complexity.
• Quadratic Equation. Individual square roots arise from quadratics, but a sum of many radicals can have algebraic degree exponential in the number of independent radicands.
• Sum of Two Squares theorem. It concerns integer representation by squared integers, not sums of square roots.
• Root Sum / sum of polynomial roots. Those problems use polynomial root sets or symmetric functions and have a different input language.
• PosSLP. PosSLP asks whether the integer output of a division-free straight-line program is positive. It is a broader arithmetic-circuit sign problem used to obtain upper bounds; it is not an alias for SSR.^[6]
• Exact zero testing. Equality of a sum of radicals is easier than sign comparison and should remain a distinct predicate.
• Unary Square-Root Sum. USSR changes the input encoding and has a distinct nonuniform upper bound.

References

[1] M. R. Garey, R. L. Graham, and D. S. Johnson, “Some NP-Complete Geometric Problems,” Proceedings of the Eighth Annual ACM Symposium on Theory of Computing (1976): 10–22. doi:10.1145/800113.803626. registry ↩a ↩b ↩c ↩d

[2] P. Tiwari, “A Problem That Is Easier to Solve on the Unit-Cost Algebraic RAM,” Journal of Complexity 8 (1992): 393–397. doi:10.1016/0885-064X(92)90003-T. registry ↩a ↩b ↩c ↩d

[3] N. Balaji and S. Datta, “USSR Is in P/poly,” 2024 Symposium on Simplicity in Algorithms (SOSA) (2024): 151–159. doi:10.1137/1.9781611977936.15; arXiv:2310.19335. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h

[4] C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra, “A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals,” Algorithmica 27 (2000): 87–99. doi:10.1007/s004530010005. registry ↩a ↩b

[5] J. Qian and C. Wang, “How Much Precision Is Needed to Compare Two Sums of Square Roots of Integers?” Information Processing Letters 100 (2006): 194–198. doi:10.1016/j.ipl.2006.05.002. registry ↩a ↩b

[6] E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen, “On the Complexity of Numerical Analysis,” SIAM Journal on Computing 38 (2009): 1987–2006. doi:10.1137/070697926. registry ↩a ↩b ↩c ↩d

[7] F. Eisenbrand, M. Haeberle, and N. Singer, “An Improved Bound on Sums of Square Roots via the Subspace Theorem,” 40^th International Symposium on Computational Geometry (SoCG 2024), LIPIcs 293, Article 54. doi:10.4230/LIPIcs.SoCG.2024.54; arXiv:2312.02057. registry ↩a ↩b ↩c

[8] M. Ajdarów, J. C. A. Main, P. Novotný, and M. Randour, “Taming Infinity One Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs,” 52^nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), LIPIcs 334, Article 138. doi:10.4230/LIPIcs.ICALP.2025.138; arXiv:2503.00788. registry ↩

[9] J. Blömer, “Computing Sums of Radicals in Polynomial Time,” Proceedings of the 32^nd Annual Symposium on Foundations of Computer Science (1991): 670–677. doi:10.1109/SFCS.1991.185434. registry ↩a ↩b ↩c

[10] K. Etessami and M. Yannakakis, “Recursive Concurrent Stochastic Games,” Logical Methods in Computer Science 4(4:7) (2008). doi:10.2168/LMCS-4(4:7)2008; arXiv:0810.3581. registry ↩a ↩b

[11] M. X. Goemans, “Semidefinite Programming in Combinatorial Optimization,” Mathematical Programming 79 (1997): 143–161. doi:10.1007/BF02614315. registry ↩