suma de radicales
En la teoría de la complejidad computacional , existe un problema abierto de si alguna información sobre una suma de radicales se puede calcular en tiempo polinomial dependiendo del tamaño de entrada, es decir, en el número de bits necesarios para representar esta suma. Es de importancia 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]
donde son 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, hay investigaciones en complejidad computacional, especialmente en álgebra computacional , 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 euclidiano más corto problema, es necesario determinar el signo de una expresión en la que se resta la longitud del primer camino 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 Monte Carlo de tiempo polinomial para determinar si una suma de radicales es cero o, de manera más general, si representa un número racional. [4] Mientras que el resultado de Blömer no resuelve la complejidad computacional de encontrar el signo de la suma de radicales, implica que si el último problema está en la clase NP , entonces también está en co-NP . [4]