Complejidad y computación real

«Complejidad y computación real» es un libro sobre la teoría de la complejidad computacional de la computación real . Estudia algoritmos cuyas entradas y salidas son números reales , utilizando la máquina de Blum-Shub-Smale como modelo de computación . Por ejemplo, esta teoría es capaz de abordar una pregunta planteada en 1991 por Roger Penrose en «La nueva mente del emperador» : «¿Es computable el conjunto de Mandelbrot ?» ^{[ 1 ]}

El libro fue escrito por Lenore Blum , Felipe Cucker , Michael Shub y Stephen Smale , con un prólogo de Richard M. Karp , y publicado por Springer-Verlag en 1998 ( doi:10.1007/978-1-4612-0701-6 , ISBN 0-387-98281-7). ^{[ 2 ]}

Stephen Vavasis observa que este libro llena un vacío significativo en la literatura: si bien los científicos informáticos teóricos que trabajan en algoritmos discretos han estado estudiando modelos de computación y sus implicaciones para la complejidad de los algoritmos desde la década de 1970, los investigadores en algoritmos numéricos, en su mayoría, no habían logrado definir su modelo de computación, dejando sus resultados sobre una base endeble. Más allá del objetivo de fundamentar mejor este aspecto del tema, el libro también tiene como objetivos presentar nuevos resultados en la teoría de la complejidad de la computación con números reales y recopilar resultados previamente conocidos en esta teoría. ^{[ 3 ]}

La introducción del libro reproduce el artículo «Complejidad y computación real: un manifiesto», publicado previamente por los mismos autores. Este manifiesto explica por qué los modelos clásicos discretos de computación, como la máquina de Turing, son inadecuados para el estudio de problemas numéricos en áreas como la computación científica y la geometría computacional , motivando así el nuevo modelo estudiado en el libro. A continuación, el libro se divide en tres partes. ^{[ 2 ]}

La primera parte del libro establece modelos de computación sobre cualquier anillo , con un costo unitario por operación de anillo. Proporciona análogos de la teoría de la recursión y del problema P versus NP en cada caso, y demuestra la existencia de problemas NP-completos de forma análoga a la demostración del teorema de Cook-Levin en el modelo clásico, que puede considerarse un caso especial de esta teoría para la aritmética módulo 2. El anillo de los enteros se estudia como un ejemplo particular, al igual que los cuerpos algebraicamente cerrados de característica cero, que se demuestran, desde el punto de vista de la NP-completitud dentro de sus modelos computacionales, como equivalentes a los números complejos . ^{[ 2 ]} ( Eric Bach señala que esta equivalencia puede considerarse una forma del principio de Lefschetz ). ^{[ 4 ]}

La Parte II se centra en algoritmos de aproximación numérica, en el uso del método de Newton para estos algoritmos y en la teoría alfa del autor Stephen Smale para la certificación numérica de la precisión de los resultados de estos cálculos. Otros temas considerados en esta sección incluyen la búsqueda de raíces de polinomios y los puntos de intersección de curvas algebraicas , el número de condición de sistemas de ecuaciones y la complejidad temporal de la programación lineal con coeficientes racionales . ^{[ 2 ]}

La Parte III proporciona análogos de la teoría de la complejidad estructural y la teoría de la complejidad descriptiva para el cálculo de números reales, incluyendo muchas separaciones de clases de complejidad que son demostrables en esta teoría, aunque las separaciones análogas en la teoría de la complejidad clásica aún no se han demostrado. Una herramienta clave en esta área es el uso del número de componentes conexas de un conjunto semialgebraico para proporcionar una cota inferior para la complejidad temporal de un problema computacional asociado. ^{[ 2 ]}

El libro está dirigido a estudiantes de posgrado o investigadores en estos temas, ^{[ 2 ] [ 3 ]} y en algunos lugares presupone conocimientos previos de teoría clásica de la complejidad computacional, geometría diferencial , topología y sistemas dinámicos . ^{[ 3 ] [ 4 ]}

El crítico Klaus Meer escribe que el libro está "muy bien escrito", "perfecto para usar a nivel de posgrado" y representa bien tanto el estado del arte en esta área como las fuertes conexiones que se pueden establecer entre campos tan diversos como la teoría algebraica de números , la geometría algebraica , la lógica matemática y el análisis numérico . ^{[ 2 ]}

Como crítica menor, dirigida más al modelo de Blum-Shub-Smale que al libro, Stephen Vavasis observa que (a diferencia de las máquinas de Turing) detalles aparentemente menores del modelo, como la capacidad de calcular las funciones piso y techo , pueden marcar grandes diferencias en lo que es computable y en la eficiencia con que se puede calcular. Sin embargo, Vavasis escribe: "esta dificultad probablemente sea inherente al tema". ^{[ 3 ]} En relación con esto, Eric Bach se queja de que asignar un costo unitario a todas las operaciones aritméticas puede dar una idea engañosa de la complejidad de un problema en la computación práctica, ^{[ 4 ]} y Vavasis también señala que, a la fecha de publicación de su reseña, este trabajo aparentemente había tenido poco efecto en la investigación práctica en computación científica . A pesar de estos problemas, recomienda el libro como un compendio conveniente y escrito con claridad de la teoría de la computación numérica. ^{[ 3 ]}

• Complejidad y computación real en el Archivo de Internet