¿Cuáles son las razones por las que los investigadores en geometría computacional prefieren el modelo BSS / RAM real?

Fondo

El cálculo sobre números reales es más complicado que el cálculo sobre números naturales, ya que los números reales son objetos infinitos y hay innumerables números reales, por lo tanto, los números reales no pueden representarse fielmente por cadenas finitas sobre un alfabeto finito.

A diferencia de la computabilidad clásica sobre cadenas finitas donde diferentes modelos de computación como: cálculo lambda, máquinas de Turing, funciones recursivas, ... resultan equivalentes (al menos para computabilidad sobre funciones en cadenas), hay varios modelos propuestos para computación sobre números reales que no son compatibles. Por ejemplo, en el modelo TTE (ver también [Wei00]), que es el más cercano al modelo clásico de máquina de Turing, los números reales se representan utilizando cintas de entrada infinitas (como los oráculos de Turing) y no es posible decidir la comparación y relaciones de igualdad entre dos números reales dados (en cantidad de tiempo finita). Por otro lado, en los modelos BBS / RAM real que son similares al modelo de máquina RAM, tenemos variables que pueden almacenar números reales arbitrarios, y la comparación y la igualdad se encuentran entre las operaciones atómicas del modelo. Por esta y otras razones similares, muchos expertos dicen que los modelos BSS / RAM real no son realistas (no se pueden implementar, al menos no en las computadoras digitales actuales), y prefieren el TTE u otros modelos equivalentes al TTE como modelo teórico de dominio efectivo, Modelo Ko-Friedman, etc.

Si entendí correctamente , el modelo de cálculo predeterminado que se utiliza en Geometría Computacional es el modelo BSS (también conocido como RAM real , ver [BCSS98]).

Por otro lado, me parece que en la implementación de los algoritmos en Geometría Computacional (por ejemplo, LEDA ), solo estamos tratando con números algebraicos y no hay objetos o cálculos infinitos de tipo superior involucrados (¿es esto correcto?). Entonces, me parece (probablemente ingenuamente) que también se puede usar el modelo clásico de computación sobre cadenas finitas para tratar con estos números y usar el modelo habitual de computación (que también se usa para la implementación de los algoritmos) para discutir la corrección y la complejidad de algoritmos

Preguntas:

¿Cuáles son las razones por las que los investigadores en Geometría Computacional prefieren usar el modelo BSS / RAM real? (Razones de geometría computacional específica para usar el modelo BSS / RAM real)

¿Cuáles son los problemas con la idea (probablemente ingenua) que he mencionado en el párrafo anterior? (usando el modelo clásico de computación y restringiendo las entradas a números algebraicos en Geometría Computacional)

Apéndice:

También existe la complejidad del problema de los algoritmos, es muy fácil decidir el siguiente problema en el modelo BSS / RAM real:

Dados dos conjuntos y de enteros positivos, ¿ es ?T ∑ s ∈ S $S$$T$
$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

Si bien no se conoce un algoritmo eficiente de RAM entera para resolverlo. Gracias a JeffE por el ejemplo.

Referencias

1. Lenore Blum, Felipe Cucker, Michael Shub y Stephen Smale, "Complejidad y computación real", 1998
2. Klaus Weihrauch, " Análisis computable, una introducción ", 2000

En primer lugar, los geómetras computacionales no lo consideran el modelo BSS. El verdadero modelo RAM fue definido por Michael Shamos en su tesis doctoral de 1978 ( Geometría computacional ), que posiblemente lanzó el campo. Franco Preparata revisó y extendió la tesis de Shamos en el primer libro de texto de geometría computacional, publicado en 1985. La RAM real también es equivalente ( excepto por la uniformidad; ¡vea la respuesta de Pascal! ) Al modelo de árbol de cálculo algebraico definido por Ben-Or en 1983. Blum Los esfuerzos de Shub y Smale se publicaron en 1989, mucho después de que se estableciera la RAM real, y la comunidad de geometría computacional los ignoró casi por completo.

La mayoría de los resultados (clásicos) en geometría computacional están fuertemente vinculados a problemas en la geometría combinatoria , para los cuales los supuestos acerca de que las coordenadas son integrales o algebraicas son (en el mejor de los casos) distracciones irrelevantes. Hablando como nativo, parece completamente natural considerar puntos arbitrarios , líneas, círculos y similares como objetos de primera clase al probar cosas sobre ellos y, por lo tanto, igualmente natural al diseñar y analizar algoritmos para computar con ellos.

Para la mayoría de los algoritmos geométricos (clásicos), esta actitud es razonable incluso en la práctica. La mayoría de los algoritmos para problemas geométricos planos se construyen sobre un número muy pequeño de primitivas geométricas: ¿está el punto a la izquierda o derecha del punto ? ¿Arriba, abajo o en la línea a través de los puntos y ? ¿Dentro, fuera o en el círculo determinado por los puntos ? Izquierda o derecha de la intersección de los segmentos y ? Cada una de estas primitivas se implementa evaluando el signo de un polinomio de bajo grado en las coordenadas de entrada. (Por lo tanto, estos algoritmos se pueden describir en la decisión algebraica más débilq q r q , r , s q r s $p$$q$$q$$r$$q,r,s$$qr$$st$ modelo de árbol). Si las coordenadas de entrada son enteras, estas primitivas pueden evaluarse exactamente con solo un aumento de factor constante en la precisión, por lo que los tiempos de ejecución en la RAM real y la RAM entera son los mismos.

Por razones similares, cuando la mayoría de las personas piensan en algoritmos de clasificación, no les importa lo que están clasificando, siempre que los datos provengan de un universo totalmente ordenado y se puedan comparar dos valores en tiempo constante.

Entonces, la comunidad desarrolló una separación de preocupaciones entre el diseño de algoritmos geométricos "reales" y su implementación práctica; De ahí el desarrollo de paquetes como LEDA y CGAL. Incluso para las personas que trabajan en el cálculo exacto, existe una distinción entre el algoritmo real , que utiliza la aritmética real exacta como parte del modelo subyacente, y la implementación , que está obligada por las limitaciones irrelevantes de los dispositivos informáticos físicos a utilizar el cálculo discreto.

Dentro de esta visión del mundo, por ejemplo, el problema abierto más importante en geometría computacional es la existencia de un algoritmo de tiempo polinómico para programación lineal. No, los métodos de elipsoide y punto interior no cuentan. A diferencia del algoritmo simplex, no se garantiza que esos algoritmos terminen a menos que la matriz de restricción sea racional. ( Existen tipos combinatorios de politopos convexos que solo pueden representarse mediante matrices de restricción irracionales , por lo que esta es una restricción no trivial). E incluso cuando la matriz de restricción es racional, los tiempos de ejecución de esos algoritmos no están limitados por ninguna función del tamaño de entrada (dimensión # restricciones).$\times$

Existen algunos algoritmos geométricos que realmente dependen en gran medida del modelo de árbol de cálculo algebraico y, por lo tanto , no se pueden implementar de manera exacta y eficiente en computadoras físicas. Un buen ejemplo son las rutas de enlace mínimo en polígonos simples, que se pueden calcular en tiempo lineal en una RAM real, pero requieren un número cuadrático de bits en el peor de los casos para representar exactamente. Otro buen ejemplo son los cortes jerárquicos de Chazelle , que se utilizan en los algoritmos más eficientes conocidos para la búsqueda de rango simplex. Estos recortes usan una jerarquía de conjuntos de triángulos, donde los vértices de los triángulos en cada nivel son puntos de intersección de líneas a través de bordes de triángulos en niveles anteriores. Por lo tanto, incluso si las coordenadas de entrada son números enteros, las coordenadas de vértice para estos triángulos son números algebraicos de grado ilimitado; sin embargo, los algoritmos para construir y usar esquejes suponen que las coordenadas se pueden manipular exactamente en tiempo constante.

Entonces, mi respuesta breve y sesgada personalmente es esta: TTE, teoría de dominio, Ko-Friedman y otros modelos de cómputo de números reales "realistas", todos abordan cuestiones que a la comunidad de geometría computacional, en general, simplemente no le importan .

No es del todo cierto que el modelo RAM / BSS real sea equivalente al modelo de árbol de cálculo algebraico. Este último es más poderoso porque un árbol de profundidad polinómica puede ser de tamaño exponencial. Esto da mucho espacio para codificar información no uniforme. Por ejemplo, Meyer auf der Heide ha demostrado que los árboles de decisión algebraicos (incluso lineales) pueden resolver problemas difíciles de manera eficiente, como la suma de subconjuntos, pero esto es (conjeturalmente) imposible en el modelo RAM / BSS real.

Aquí hay un comentario sobre la excelente respuesta de Jeff:

Se propusieron nociones de condición, aproximación y redondeo para abordar la brecha de complejidad (combinatoria versus continua) de los algoritmos de programación lineal. La condición de una instancia de problema estima el efecto de pequeñas perturbaciones de la entrada en la precisión de la salida. La noción de condición fue introducida por primera vez por Alan Turing. Jim Renegar introdujo la noción de condición de un programa lineal.

L. BLUM, Informática sobre los reales: ¿Dónde se reúne Turing Newton, , AVISOS DE LA AMS, Volumen 51, Número 9, (2004), 1024-1034

A. TURING, errores de redondeo en procesos matriciales, Quart. J. Mech. Appl. Mates. 1 (1948), 287–308

J. RENEGAR, Incorporando números de condición en la teoría de la complejidad de la programación lineal, SIAM J. Optim. 5 (1995), 506-524

F. CUCKER y J. PEÑA, un algoritmo primal-dual para resolver sistemas cónicos poliédricos con una máquina de precisión finita, SIAM Journal on Optimization 12 (2002), 522–554.