¿Cómo se especifican los números reales en el cálculo?

27

Esta puede ser una pregunta básica, pero he estado leyendo y tratando de entender documentos sobre temas como el cálculo de equilibrio de Nash y las pruebas de degeneración lineal y no he estado seguro de cómo se especifican los números reales como entrada. Por ejemplo, cuando se afirma que LDT tiene ciertos límites inferiores polinómicos, ¿cómo se especifican los números reales cuando se tratan como entrada?

cc.complexity-theory computability na.numerical-analysis computing-over-reals computable-analysis Philip White
fuente
1
Puede encontrar la discusión aquí de interés: en.wikipedia.org/wiki/Computable_number
Joseph Malkevitch
Alguien debería juntar estos documentos en un libro electrónico descargable gratuito.
Dilawar

Respuestas:

34

No estoy de acuerdo con tu respuesta aceptada por Kaveh. Para la programación lineal y los equilibrios de Nash, el punto flotante puede ser aceptable. Pero los números de coma flotante y la geometría computacional se mezclan muy mal: el error de redondeo invalida los supuestos combinatorios de los algoritmos, lo que con frecuencia hace que se bloqueen. Más específicamente, muchos algoritmos de geometría computacional dependen de pruebas primitivas que verifican si un valor dado es positivo, negativo o cero. Si ese valor está muy cerca de cero y el redondeo de punto flotante hace que tenga el signo incorrecto, pueden suceder cosas malas.

En cambio, a menudo se supone que las entradas tienen coordenadas enteras, y los resultados intermedios a menudo se representan exactamente, ya sea como números racionales con precisión suficientemente alta para evitar el desbordamiento o como números algebraicos. Las aproximaciones de punto flotante a estos números se pueden usar para acelerar los cálculos, pero solo en situaciones en las que se puede garantizar que los números estén lo suficientemente lejos de cero como para que las pruebas de signos den las respuestas correctas.

En la mayoría de los documentos de algoritmos teóricos en geometría computacional, este problema se evita asumiendo que las entradas son números reales exactos y que las primitivas son pruebas exactas de los signos de raíces de polinomios de bajo grado en los valores de entrada. Pero si está implementando algoritmos geométricos, todo esto se vuelve muy importante.

David Eppstein
fuente
Me gustó la parte de la respuesta de Kaveh donde sugirió que hay modelos alternativos de cómputo, ya que esto parecía estar en línea con lo que había leído en el periódico que estaba mirando. Dicho eso, realmente no sabía la respuesta ... No acepté la respuesta de Kaveh por ahora. De hecho, había sospechado que los números algebraicos podrían tener algo que ver con eso. De todos modos, gracias por tomarse el tiempo para evaluar mi pregunta ... Pensaré y leeré más antes de aceptar una respuesta.
Philip White
No he dicho que sea un buen modelo para CG, mi punto fue que incluso cuando los autores dicen que las entradas son números reales, en realidad no son números reales . Estoy de acuerdo con usted en que no debería haber incluido CG entre los demás. He leído un número muy pequeño de documentos CG, ¿el modelo BSS está bien establecido en los documentos teóricos CG?
Kaveh
1
Disculpe mi ignorancia, pero ¿qué significa BSS?
Philip White
1
El modelo BSS es un modelo teórico que asume que hay números reales arbitrarios disponibles. Lo que se hace en CG implica implementaciones reales de un modelo que generalmente está restringido a números algebraicos. Además, las implementaciones de CG están lejos del costo unitario por operación. Entonces no son lo mismo. Ver, por ejemplo, el modelo de número real LEDA, citeseerx.ist.psu.edu/viewdoc/…
David Eppstein
10
@Kaveh: No. Los algoritmos geométricos están diseñados para ser correctos, en el modelo de RAM real, para una entrada real arbitraria, no solo para una entrada racional. En particular, hay algoritmos geométricos que no pueden implementarse exactamente, porque usan primitivas que son triviales en la RAM real pero para las cuales no se conoce un algoritmo eficiente para la RAM entera (realista). El mejor ejemplo es la suma del problema de raíces cuadradas: dados dos conjuntos y T de enteros positivos, es ∑ s ∈ S √ST ? ∑s∈Ss>∑t∈Tt
Jeffε
8

Esta no es una respuesta directa a su pregunta, sino más bien una respuesta a Rafael . Ha habido bastante trabajo recientemente especificando cálculos de números reales usando coinducción. Aquí hay algunos artículos sobre el tema.

Apenas cubren el espectro completo del cómputo de números reales, pero se está avanzando para eliminar varios problemas.

Dave Clarke
fuente
1
R
Buen punto. No estoy seguro de cuáles son las limitaciones del enfoque coinductivo. El enfoque está en su infancia.
Dave Clarke
7

Blum, Cucker, Shub y Smale consideran la complejidad computacional de los cálculos sobre números reales . Aquí hay una descripción parcial del libro:

La teoría clásica de la computación tiene su origen en el trabajo de Goedel, Turing, Church y Kleene y ha sido un marco extraordinariamente exitoso para la informática teórica. La tesis de este libro, sin embargo, es que proporciona una base inadecuada para la computación científica moderna donde la mayoría de los algoritmos son algoritmos de números reales. El objetivo de este libro es desarrollar una teoría formal de la computación que integre los principales temas de la teoría clásica y que sea más directamente aplicable a problemas matemáticos, análisis numéricos y computación científica. En el camino, los autores consideran problemas tan fundamentales como: ¿El conjunto de Mandelbrot es decidible? Para mapas cuadráticos simples, ¿es el conjunto de Julia un conjunto detenido? ¿Cuál es la verdadera complejidad de Newton? s método? ¿Existe un algoritmo para decidir el problema de la mochila en un número plinomial de pasos? ¿Es intratable el Hilbert Nullstellensatz? ¿Es el problema de localizar un cero real de grado cuatro polinomial intratable? ¿La programación lineal es manejable sobre los reales?

Puede encontrar una reseña de este libro en ACM SIGACT News .

MS Dousti
fuente
Este libro se ve muy interesante, gracias.
Philip White el
Eres bienvenido.
MS Dousti
55
Vale la pena señalar que el modelo de cómputo BSS sobre los reales es controvertido, por razones muy parecidas a las que David Eppstein mencionó en un comentario anterior. Por ejemplo: el axioma de BSS que calcula si x <y toma un paso de tiempo, para reales arbitrarios x e y. Por el contrario, enfoques como la eficacia de tipo dos (TTE) definen máquinas que toman como aproximaciones de entrada a los reales, y generan aproximaciones computables de salida a las funciones sobre los reales. Cuanto más tiempo transcurra, mejores serán las aproximaciones de entrada y salida. Ese enfoque me parece más realista.
Aaron Sterling
@ Aaron Sterling: ¿conoces una buena referencia para la efectividad del tipo dos?
Joshua Grochow
3
@ Joshua Grochow: Lo siento, no llegué a esto antes. El libro al que Kaveh se unió es "Nielsen and Chuang" de TTE. Sin embargo, está tan cargado de anotaciones que parecería arcano para un lector casual. Sugeriría, en cambio, las siguientes diapositivas del tutorial de Vasco Brattka: cca-net.de/vasco/cca/tutorial.pdf
Aaron Sterling el
7

Editado / corregido en base a los comentarios

Cuando los autores hablan sobre entradas de números reales en la programación lineal, cálculo de equilibrio de Nash, ... en la mayoría de los artículos (documentos que no tratan el tema de la computación / complejidad sobre los números reales), en realidad no significan números reales. Son números racionales y números que surgen de ellos debido a sus manipulaciones (números algebraicos). Entonces puede pensar en ellos como representados por cadenas finitas.

Por otro lado, si el documento trata sobre la computabilidad y la complejidad en el análisis , entonces no están utilizando el modelo habitual de computación, y existen varios modelos incompatibles de computación / complejidad sobre números reales.

Si el documento no especifica un modelo de cálculo sobre números reales, puede asumir con seguridad que es el primer caso, es decir, son solo números racionales.

La geometría computacional es diferente. En la mayoría de los trabajos en CG, si los autores no especifican cuál es el modelo que se está discutiendo con respecto a la corrección y complejidad de un algoritmo, se puede suponer que es el modelo BSS (también conocido como RAM real).

El modelo no es realista y, por lo tanto, la implementación no es sencilla. (Esta es una de las razones por las que algunas personas en CCA prefieren los modelos teóricos Ko-Friedman / TTE / Domain , pero el problema con estos modelos es que en la práctica no son tan rápidos como el cálculo de punto flotante). La corrección y complejidad de El algoritmo en el modelo BSS no se transfiere necesariamente a la corrección del algoritmo implementado.

El libro de Weihrauch contiene una comparación entre diferentes modelos (Sección 9.8). Son solo tres páginas y vale la pena leerlas.

(También hay una tercera forma, que puede ser más adecuada para CG, es posible que desee echar un vistazo a este documento:

Chee Yap, " Teoría de la computación real según EGC "

donde EGC es computación geométrica exacta ).

Kaveh
fuente
Creo que el trabajo en el que estoy interesado principalmente especifica un modelo, dado que incluye la oración "Ahora definimos formalmente nuestro modelo de cálculo". El documento se llama "Límites más bajos para problemas de satisfacción", y parece haber cierta discusión sobre los árboles de decisión lineal y los polinomios de consulta. Entonces, creo que esa es la respuesta que estaba buscando allí ... gracias. Volveré a leer el periódico y veré si puedo darle sentido.
Philip White el
2
Estoy en desacuerdo. Este es el modelo incorrecto para la geometría computacional. Vea mi respuesta más detallada a continuación.
David Eppstein
1
@Kaveh: Creo que debería decir que son números racionales , no números de punto flotante. Los números racionales exactos son fáciles de representar mediante cadenas finitas, y en muchas aplicaciones (por ejemplo, las relacionadas con la programación lineal) los resultados intermedios también serán números racionales si sus entradas son números racionales. (Por supuesto, como señaló David Eppstein, comp. Geom. Es una notable excepción en el sentido de que los resultados intermedios generalmente no son racionales).
Jukka Suomela
@ Jukka: Tienes razón, reemplazaré el punto flotante con racional
Kaveh
55
No Cuando escribo "número real", me refiero a "número real", y con esto me refiero a realmente número real, de verdad de los reales. De Verdad. En particular, en el artículo del que habla @Philip, tengo que asumir que los algoritmos funcionan para una entrada real arbitraria , de modo que pueda aplicar los resultados del análisis no estándar.
Jeffε
3

No son y no pueden, en general. Solo podemos tratar un número contable de entradas (y salidas y funciones) con nuestros modelos de cálculo. En particular, cualquier entrada debe ser finita, pero no todos los números reales tienen representaciones finitas.

Supongo que podría suponer algún tipo de oráculo que arroje el siguiente dígito de un cierto número real a pedido (algo así como una secuencia). De lo contrario, tendrá que vivir con aproximaciones (arbitrariamente precisas).

Rafael
fuente
Si esto es cierto, ¿cómo puede LDT lidiar con números reales? Leí algo sobre "Árboles de decisión lineales r", pero realmente no entendí de qué estaban hablando en el documento, "Límites inferiores para problemas de satisfacción lineal".
Philip White
Apuesto a que no pueden o no usan máquinas de Turing (o conecpts equivalentes). Las otras respuestas que no son tan estrictas / generales como las mías deberían arrojar algo de luz sobre esto.
Raphael