En la teoría de la complejidad computacional , existe el problema abierto de si cierta información sobre una suma de radicales puede calcularse en tiempo polinomial dependiendo del tamaño de entrada, es decir, del número de bits necesarios para representar esta suma. Es importante para muchos problemas de geometría computacional , ya que el cálculo de la distancia euclidiana entre dos puntos en el caso general implica el cálculo de una raíz cuadrada y, por lo tanto, el perímetro de un polígono o la longitud de una cadena poligonal toma la forma de una suma de radicales. [1]
La suma de radicales se define como una combinación lineal finita de radicales:
donde están los números naturales y son los números reales .
La mayor parte de la investigación teórica en geometría computacional de carácter combinatorio asume el modelo computacional de RAM real de precisión infinita, es decir, una computadora abstracta en la que los números reales y las operaciones sobre ellos se realizan con precisión infinita y el tamaño de entrada de un número real y el costo de un operación elemental son constantes. [2] Sin embargo, existen investigaciones en complejidad computacional, especialmente en álgebra informática , donde el tamaño de entrada de un número es el número de bits necesarios para su representación. [3]
De particular interés en geometría computacional es el problema de determinar el signo de la suma de radicales . Por ejemplo, la longitud de un camino poligonal en el que todos los vértices tienen coordenadas enteras se puede expresar usando el teorema de Pitágoras como una suma de raíces cuadradas enteras, por lo que para determinar si un camino es más largo o más corto que otro en un camino más corto euclidiano problema, es necesario determinar el signo de una expresión en la que la longitud del primer camino se resta del segundo; esta expresión es una suma de radicales.
De manera similar, el problema de la suma de radicales es inherente al problema de la triangulación de peso mínimo en la métrica euclidiana .
En 1991, Blömer propuso un algoritmo de Monte Carlo de tiempo polinomial para determinar si una suma de radicales es cero o, más generalmente, si representa un número racional. [4] Si bien el resultado de Blömer no resuelve la complejidad computacional de encontrar el signo de la suma de radicales, sí implica que si este último problema está en la clase NP , entonces también está en co-NP . [4]
![{\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88f8e5154b52c32759c00bcfd8940b97ad925b4f)
