37
$\begingroup$

The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater than the sum $\sum_i \sqrt{b_i}$. The complexity status of this problem is open; see this post for further details. This problem arises naturally in computational geometry, especially in problems involving Euclidean shortest paths, and is a significant stumbling block in transferring algorithms for those problems from the real RAM to the standard integer RAM.

Call a problem Π sum-of-square-roots-hard (abbreviated Σ√-hard?) if there is a polynomial-time reduction from the sum of square roots problem to Π. It is not hard to prove that the following problem is sum-of-square-roots-hard:

Shortest paths in 4d Euclidean geometric graphs

Instance: A graph $G=(V,E)$ whose vertices are points in $\mathbb{Z}^4$, with edges weighted by Euclidean distane; two vertices $s$ and $t$

Output: The shortest path from $s$ to $t$ in $G$.

Of course this problem can be solved in polynomial-time on the real RAM using Dijkstra's algorithm, but each comparison in that algorithm requires solving a sum-of-square-roots problem. The reduction uses the fact that any integer can be written as the sum of four perfect squares; the output of the reduction is actually a cycle on $2n+2$ vertices.

What other problems are sum-of-square-roots-hard? I'm particularly interested in problems for which there is a polynomial-time solution on the real RAM. See my previous question for one possibility.

As Robin suggests, boring answers are boring. For any complexity class X that contains sum-of-square-roots (for example, PSPACE or EXPTIME), every X-hard problem is boringly sum-of-square-roots-hard.

$\endgroup$
  • 1
    $\begingroup$ Thanks to Suresh and Peter for suggesting this question. $\endgroup$ – Jeffε Jan 1 '11 at 17:38
  • 8
    $\begingroup$ Perhaps you could also rule out trivial answers by insisting that the answers shouldn't just be problems that are hard for a class that's known to contain the Sum-of-square-roots problem. For example, any PSPACE-hard problem would be Sum-of-square-roots-hard, but that's probably not interesting. $\endgroup$ – Robin Kothari Jan 1 '11 at 17:58
  • $\begingroup$ Do you really mean $\mathbb{R}^4$ in your shortest-paths problem statement, or $\mathbb{Z}^4$? The former doesn't seem like it could use an integer RAM at all, and presumably the problem is still Σ√-hard restricting to integer points... $\endgroup$ – Steven Stadnicki Jan 3 '11 at 19:37
  • $\begingroup$ @Steven: Yup, you're right. Edited. $\endgroup$ – Jeffε Jan 6 '11 at 5:08
18
$\begingroup$

This was discussed a bit in the following survey (starting slide 21): http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf

which mentions Euclidean TSP, approximation of actual Nash equilibrium, and talks about the classes PosSLP and FIXP.

$\endgroup$
  • 1
    $\begingroup$ this is a fascinating connection. $\endgroup$ – Suresh Venkat Jan 3 '11 at 22:16
21
$\begingroup$

This should be a comment, as it is a mostly boring answer, but I don´t have enough reputation.

The sum of square roots problem is in $P^{PP^{PP^{PP}}}$ from [ABKM98], so any problem hard for this class has the required property. This is done by reducing the sum-of-square-roots problem to a problem called $PosSLP$, defined as deciding whether a straight-line problem represents a positive integer, so that problem is sum-of-square-roots hard.

[ABKM98]: On the Complexity of Numerical analysis, by Allender, Burgisser, Kjeldgaard-Pedersen and Miltersen.

$\endgroup$
  • 9
    $\begingroup$ There is also this improvement [mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf] that puts the problem in ${CoRP}^{PP}$ and also proves that a restricted version of the problem needs a polynomial number of bits. $\endgroup$ – Elias Jan 2 '11 at 8:07
  • 1
    $\begingroup$ @Elias: Can you elaborate? From a cursory look, Kayal and Saha seem to be discussing the “polynomial version” of the sum of square roots problem, which is related to but different from the usual sum of square roots problem. $\endgroup$ – Tsuyoshi Ito Jan 4 '11 at 5:52
  • 1
    $\begingroup$ @Abel: (1) Hi Abel, glad to see your post! (2) For what it’s worth, [ABKM98] was actually presented at CCC 2006 and published in 2009. (3) A boring answer should not be a comment but should be kept to yourself. But I do not think that this is a boring answer. :) $\endgroup$ – Tsuyoshi Ito Jan 4 '11 at 6:07
  • 1
    $\begingroup$ @Tsuyoshi: They solved completely the polynomial version of the problem. Based on this they prove that if $a_i$ are of special form, i.e. $a_i=\sum_i{b_ij}X^{d_i-j}$ where $X>(B+1)^{(nd)^{O(1)}}$, $B=max\{b_{ij}\}$ and $d=max\{d_i\}$, then we need a polynomial number of bits to decide the problem. $\endgroup$ – Elias Jan 4 '11 at 12:16
  • 3
    $\begingroup$ @Tsuyoshi: I completely misunderstood your question. I am sorry for this. What Kayal and Saha prove is that DegSLP is in $CoRP^{PP}$. I should be more careful. Thank you for this. $\endgroup$ – Elias Jan 4 '11 at 21:35

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.