9
$\begingroup$

In [1], Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP.

Given integers $a_1, a_2, \ldots, a_n$ and $L$, determine if $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

They observe that it is not even apparent that this problem is in NP since it is not clear what the minimum digits of precision are required in the computation of the square roots to sufficiently compare the sum to $L$. However, they do cite a best known upper bound of $O(m2^n)$ where $m$ is "the number of digits in the original symbolic expression". Unfortunately, this upper bound is attributed merely to a personal communication from A. M. Odlyzko.

Does anyone have a proper reference to this upper bound? Or, in the absence of a published reference, a proof or proof sketch would also be helpful.

Note: I believe that this bound might be inferred as a consequence of more general results by Bernikel et. al. [2] from around 2000 on separation bounds for a larger class of arithmetic expressions. I'm mostly interested in more contemporaneous references (i.e.: what was known circa 1976) and/or proofs specialized to just the case of the sum of square roots.

  1. Garey, Michael R., Ronald L. Graham, and David S. Johnson. "Some NP-complete geometric problems." Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976.

  2. Burnikel, Christoph, et al. "A strong and easily computable separation bound for arithmetic expressions involving radicals." Algorithmica 27.1 (2000): 87-99.

$\endgroup$
7
$\begingroup$

Here is a rather sloppy proof sketch. Let $S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ where $\delta_i \in \{\pm 1\}$. This is an algebraic number of degree at most $2^n$ and height at most $H = (max(a_i))^{n}$. Now it is easy to check if $S = 0$ (can be done even in $TC^0$ -- see this).If $S \neq 0$ then it is bounded away from $0$ by a quantity (because it is an algebraic number and hence is a non-zero root of a univariate polynomial) that is a function of the degree and height of the minimal polynomial of $S$. Unfortunately, the dependence on the degree is exponential in the number of square roots (and if the $a_i$'s are distinct primes, this degree bound is even tight, though that case of sign evaluation is easy to handle). The precision needed is hence exponential in the number of square roots, which is $2^n$-bits for $S$. It now suffices to truncate each of the $\sqrt{a_i}$ to say $2^{10n}$ bits to ensure the sign is guaranteed to be correct. This is easily done via polynomially many steps of Newton iteration). Now it is down to checking if the sum is positive, which is just addition and hence linear in the number of bits in the summands. Notice that this computation is in Polynomial time on a BSS machine. Also notice that we are not doing any computation directly with the minimal polynomial of $S$ itself, which could have huge coefficients and look ugly, we just use it to reason about the precision to which we need to truncate the square roots. For more details, check Tiwari's paper.

$\endgroup$
  • $\begingroup$ Downvoted because the only part of this long answer that actually addresses the question is the last line, and it's a reference from 1992 not the 1970s or earlier. $\endgroup$ – David Eppstein Aug 1 at 20:58
  • 2
    $\begingroup$ @david I was just trying to provide a proof sketch for why we need 2^n- bit precision for evaluating the square roots (@mhum asked for it at some point). I'm not familiar with how such a bound was derived earlier before the paper I cited (though I suspect it should use similar techniques). $\endgroup$ – Nikhil Aug 1 at 21:10
  • $\begingroup$ Maybe it's just me, but when a question says "I know how to prove this but can someone give me a reference" I find answers showing how to prove it irritating. It's like when students on an exam give an answer to something different than what was asked, hoping (in vain) that they'll get partial credit for knowing something even though they didn't know what you wanted them to. $\endgroup$ – David Eppstein Aug 1 at 23:04
  • 8
    $\begingroup$ Don't know where you're quoting from but there's a "Does anyone have a proper reference to this upper bound? Or, in the absence of a published reference, a proof or proof sketch would also be helpful." Somewhere in the question $\endgroup$ – Nikhil Aug 2 at 4:12
  • $\begingroup$ This seems to me plausibly close enough to what could have been in the personal communication. Thanks. (I suppose I could have tried to contact Odlyzko directly to find out) $\endgroup$ – mhum Aug 2 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.