Problema de suma de raíz cuadrada

El problema de la suma de la raíz cuadrada (SRS) es un problema de decisión computacional del campo del análisis numérico , con aplicaciones a la geometría computacional .

El SRS se define de la siguiente manera: ^[1]

Dados números enteros positivos y un entero t , decida si .${\displaystyle a_{1},\ldots ,a_{k}}$${\displaystyle \suma _{i=1}^{k}{\sqrt {a_{i}}}\leq t}$

Una definición alternativa es:

Dados números enteros positivos y , decida si .${\displaystyle a_{1},\ldots ,a_{k}}$${\displaystyle b_{1},\ldots ,b_{k}}$${\displaystyle \suma _{i=1}^{k}{\sqrt {a_{i}}}\leq \suma _{i=1}^{k}{\sqrt {b_{i}}}}$

El problema se planteó en 1981 ^[2] y probablemente antes.

El SRS se puede resolver en tiempo polinomial en el modelo Real RAM . ^[3] Sin embargo, su complejidad en tiempo de ejecución en el modelo de máquina de Turing está abierta, a partir de 1997. ^[1] La principal dificultad es que, para resolver el problema, las raíces cuadradas deben calcularse con una alta precisión, lo que puede requerir una gran cantidad de bits. El problema se menciona en el Jardín de problemas abiertos. ^[4]

Blomer ^{[5] presenta un} algoritmo de Monte Carlo en tiempo polinomial para decidir si una suma de raíces cuadradas es igual a cero. El algoritmo se aplica de manera más general a cualquier suma de radicales .

Allender, Burgisser, Pedersen y Miltersen ^[6] demuestran que SRS se encuentra en la jerarquía de conteo (que está contenida en PSPACE ).

Una forma de resolver el SRS es probar un límite inferior en la diferencia absoluta o . Dicho límite inferior se denomina "límite de separación", ya que separa la diferencia de 0. Por ejemplo, si la diferencia absoluta es al menos 2 ^{- d} , significa que podemos redondear todos los números a d bits de precisión y resolver el SRS en un polinomio de tiempo en d . ${\displaystyle \left|t-\suma _{i=1}^{k}{\sqrt {a_{i}}}\right|}$${\displaystyle \left|\suma _{i=1}^{k}{\sqrt {a_{i}}}-\suma _{i=1}^{k}{\sqrt {b_{i}}}\right|}$

Esto nos lleva al problema matemático de probar límites en esta diferencia. Definamos r ( n , k ) como el valor positivo más pequeño de la diferencia , donde a _i y b _i son números enteros entre 1 y n ; definamos R ( n , k ) como -log r ( n , k ), que es el número de dígitos de precisión necesarios para resolver SRS. Calcular r ( n , k ) es el problema abierto 33 en el proyecto de problemas abiertos. ^[7]${\displaystyle \suma _{i=1}^{k}{\sqrt {a_{i}}}-\suma _{i=1}^{k}{\sqrt {b_{i}}}}$

En particular, es interesante saber si r( n , k ) está en O(poly( k ,log( n )). Una respuesta positiva implicaría que la métrica simple simple se puede resolver en tiempo polinomial en el modelo de la máquina de Turing. Algunos límites conocidos actualmente son:

• Qian y Wang ^[8] demuestran mediante una construcción explícita que, para cualquier k y n , , por lo que . Este número es óptimo para k = 2, y también para un amplio rango de números enteros.${\displaystyle r(n,k)\en O(n^{-2k+3/2})}$${\displaystyle R(n,k)\geq (2k-3/2)\cdot \log {n}}$
• Burnikel, Fleischer, Mehlhorn y Schirra ^[9] demostraron un límite superior para el número de dígitos: .${\displaystyle R(n,k)\en O(2^{2k}\cdot \log {n})}$
• Cheng, Meng, Sun y Chen ^[10] demostraron que .${\displaystyle R(n,k)\in 2^{O(n/\log {n})}\cdot \log {n}}$
• Cheng y Li ^[11] demostraron que . Esto implica que SRS se puede resolver en tiempo , siempre que n esté en o( k log k ). También presentan un algoritmo para calcular r ( n , k ) en tiempo .${\displaystyle R(n,k)\in 2^{O(n/\log {n})}}$${\displaystyle 2^{o(k)}\cdot (\log {n})^{O(1)}}$${\displaystyle n^{k+o(k)}}$
• Eisenbrand, Haeberle y Singer ^[12] demuestran que , donde gamma es una constante que depende de las entradas a ₁ ,..., a _n , y de los pasos del teorema del subespacio . Esto mejora el límite anterior .${\displaystyle r(n,k)\geq \gamma \cdot n^{-2n}}$${\displaystyle r(n,k)\geq \left(n\cdot \max _{i}({\sqrt {a_{i}}})\right)^{-2^{n}}}$

SRS es importante en geometría computacional , ya que las distancias euclidianas se dan por raíces cuadradas, y muchos problemas geométricos (por ejemplo, el árbol de expansión mínimo en el plano y el problema del viajante euclidiano ) requieren calcular sumas de distancias.

Etessami y Yannakakis ^[13] muestran una reducción de SRS al problema de la terminación de juegos estocásticos concurrentes recursivos .

El SRS también tiene una importancia teórica, ya que es un caso especial simple de un problema de viabilidad de programación semidefinida . Considere la matriz . Esta matriz es semidefinida positiva si y solo si , si y solo si . Por lo tanto, para resolver el SRS, podemos construir un problema de viabilidad con n restricciones de la forma , y restricciones lineales adicionales . El SDP resultante es factible si y solo si el SRS es factible. Como la complejidad de tiempo de ejecución del SRS en el modelo de máquina de Turing es abierta, lo mismo es cierto para la viabilidad del SDP (a partir de 1997). ${\displaystyle \left({\begin{matrix}1&x\\x&a\end{matrix}}\right)}$${\displaystyle a-x^{2}\geq 0}$${\displaystyle |x|\leq {\sqrt {a}}}$${\displaystyle \left({\begin{matrix}1&x_{i}\\x_{i}&a_{i}\end{matrix}}\right)\succeq 0}$${\displaystyle x_{i}\geq 0,\sum _{i=1}^{n}x_{i}\geq k}$

Kayal y Saha ^[14] extienden el problema de los números enteros a los polinomios . Sus resultados implican una solución de SRS para una clase especial de números enteros.