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

<p>The sum of square roots problem is in $P^{PP^{PP^{PP}}}$ from <a href="http://www-math.uni-paderborn.de/agpb/work/focs7.pdf">[ABKM98]</a>, 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.</p>

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

CC BY-SA 2.5
2011-01-02T08:07:19.633Z
There is also this improvement [http://www.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.
Elias
CC BY-SA 2.5
2011-01-04T05:52:28.823Z
@Elias: Can you elaborate?  From a cursory look, [Kayal and Saha](http://www.mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf) 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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-04T06:07:47.677Z
@Abel: (1) Hi Abel, glad to see your post!  (2) For what it’s worth, [ABKM98] was actually presented at [CCC 2006](http://dx.doi.org/10.1109/CCC.2006.30) and [published in 2009](http://dx.doi.org/10.1137/070697926).  (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. :)
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-04T12:16:07.243Z
@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.
Elias
CC BY-SA 2.5
2011-01-04T20:30:04.610Z
@Elias: Thanks, but I know that.  How does it put the (unrestricted) integer version in coRP^PP?
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-04T21:35:34.270Z
@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.
Elias
CC BY-SA 2.5
2011-01-02T01:10:26.553Z
2011-01-02T01:10:26.553Z
Abel Molina
<p>This was discussed a bit in the following survey (starting slide 21): <a href="http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf">http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf</a></p>

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

CC BY-SA 2.5
2011-01-03T22:16:56.537Z
this is a fascinating connection.
Suresh Venkat
CC BY-SA 2.5
2011-01-03T04:26:02.493Z
2011-01-03T04:26:02.493Z
Noam
<p>The <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010">sum of square roots</a> 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 <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010">this post</a> 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.</p>

<p>Call a problem Π <em>sum-of-square-roots-hard</em> (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:</p>

<blockquote>
  <p><strong>Shortest paths in 4d Euclidean geometric graphs</strong></p>
  
  <p>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$</p>
  
  <p>Output: The shortest path from $s$ to $t$ in $G$.</p>
</blockquote>

<p>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.</p>

<p><strong>What other problems are sum-of-square-roots-hard?</strong>  I'm particularly interested in problems for which there is a polynomial-time solution on the real RAM.  See 
<a href="https://cstheory.stackexchange.com/questions/4034/complexity-of-computing-shortest-paths-in-the-plane-with-polygonal-obstacles">my previous question</a> for one possibility.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-01T17:38:45.107Z
Thanks to Suresh and Peter for suggesting this question.
Jeffε
<ds.algorithms><big-list><reductions><computing-over-reals>
Sum-of-square-roots-hard problems?
Jeffε
# Sum-of-square-roots-hard problems?

(Asked by: username_0 on 2011-01-01)

The [sum of square roots](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010) 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](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010) 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](https://cstheory.stackexchange.com/questions/4034/complexity-of-computing-shortest-paths-in-the-plane-with-polygonal-obstacles) 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.

**Tags:** ds.algorithms, big-list, reductions, computing-over-reals

> **Comments:**
> **username_0**: Thanks to Suresh and Peter for suggesting this question.  

---

## 2 answers

### Answer by username_4 on 2011-01-03. Score: 19 | Accepted answer

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.

> **Comments:**
> **username_5**: this is a fascinating connection.  

---

### Answer by username_1 on 2011-01-02. Score: 22

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]](http://www-math.uni-paderborn.de/agpb/work/focs7.pdf), 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.

> **Comments:**
> **username_2**: There is also this improvement [http://www.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.  
> **username_3**: @username_2: Can you elaborate?  From a cursory look, [Kayal and Saha](http://www.mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf) 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.  
> **username_3**: @Abel: (1) Hi Abel, glad to see your post!  (2) For what it’s worth, [ABKM98] was actually presented at [CCC 2006](http://dx.doi.org/10.1109/CCC.2006.30) and [published in 2009](http://dx.doi.org/10.1137/070697926).  (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. :)  
> **username_2**: @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.  
> **username_3**: @username_2: Thanks, but I know that.  How does it put the (unrestricted) integer version in coRP^PP?  
> **username_2**: @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.  

---

