¿Problemas de suma de raíces cuadradas difíciles?

El problema de la suma de las raíces cuadradas pregunta, dadas dos secuencias y de enteros positivos, si la suma $a_1, a_2, \dots, a_n$ $b_1, b_2, \dots, b_n$ menor que, igual o mayor que la suma $\sum_i \sqrt{a_i}$ . El estado de complejidad de este problema es abierto; Veaesta publicaciónpara más detalles. Este problema surge naturalmente en la geometría computacional, especialmente en problemas que involucran caminos más cortos euclidianos, y es un obstáculo significativo en la transferencia de algoritmos para esos problemas desde la RAM real a la RAM entera estándar. $\sum_i \sqrt{b_i}$

Llame a un problema Π suma-de-raíces-cuadradas-duro (abreviado Σ√-duro?) Si hay una reducción del tiempo polinómico de la suma del problema de raíces cuadradas a Π. No es difícil demostrar que el siguiente problema es la suma de las raíces cuadradas:

Trayectos más cortos en gráficos geométricos euclidianos 4d

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.

¿Qué otros problemas son la suma de las raíces cuadradas difíciles? Estoy particularmente interesado en los problemas para los que hay una solución de tiempo polinómico en la RAM real. Vea mi pregunta anterior para una posibilidad.

Como Robin sugiere, las respuestas aburridas son aburridas. Para cualquier clase de complejidad X que contenga la suma de las raíces cuadradas (por ejemplo, PSPACE o EXPTIME), cada problema de X-hard es aburridamente la suma de las raíces cuadradas.

ds.algorithms big-list reductions computing-over-reals Jeffε
fuente

Thanks to Suresh and Peter for suggesting this question.

Jeffε

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.

Robin Kothari

Do you really mean

R^{4}

$\mathbb{R}^4$ in your shortest-paths problem statement, or

Z^{4}

$\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...

Steven Stadnicki

@Steven: Yup, you're right. Edited.

Jeffε

Respuestas:

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.

Noam
fuente

this is a fascinating connection.

Suresh Venkat

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.

Abel Molina
fuente

There is also this improvement [mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf] that puts the problem in

{C o R P}^{P P}

${CoRP}^{PP}$ and also proves that a restricted version of the problem needs a polynomial number of bits.

Elias

@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.

Tsuyoshi Ito

@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. :)

Tsuyoshi Ito

@Tsuyoshi: They solved completely the polynomial version of the problem. Based on this they prove that if

a_{i}

$a_i$ are of special form, i.e.

a_{i} = \sum_{i} b_{i} j X^{d_{i} - j}

$a_i=\sum_i{b_ij}X^{d_i-j}$ where

X > (B + 1)^{(n d)^{O (1)}}

$X>(B+1)^{(nd)^{O(1)}}$ ,

B = m a x {b_{i j}}

$B=max\{b_{ij}\}$ and

d = m a x {d_{i}}

$d=max\{d_i\}$ , then we need a polynomial number of bits to decide the problem.

Elias

@Tsuyoshi: I completely misunderstood your question. I am sorry for this. What Kayal and Saha prove is that DegSLP is in

C o R P^{P P}

$CoRP^{PP}$ . I should be more careful. Thank you for this.

Elias