Complexity and Real Computation 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 su modelo de computación . Por ejemplo, esta teoría es capaz de abordar una pregunta planteada en 1991 por Roger Penrose en The Emperor's New Mind : "¿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 importante en la literatura: aunque 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 parte no han logrado definir su modelo de computación, dejando sus resultados sobre una base inestable. Más allá del objetivo de hacer que este aspecto del tema sea más sólido, el libro también tiene como objetivo 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 discretos clásicos 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 el modelo más nuevo estudiado en el libro. A continuación, el libro se divide en tres partes. [2]
La Parte I del libro establece modelos de computación sobre cualquier anillo , con 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 prueba la existencia de problemas NP-completos de manera análoga a la prueba del teorema de Cook-Levin en el modelo clásico, que puede verse como el caso especial de esta teoría para la aritmética módulo-2 . El anillo de números enteros se estudia como un ejemplo particular, al igual que los cuerpos algebraicamente cerrados de característica cero, que se muestra desde el punto de vista de la NP-completitud dentro de sus modelos computacionales como todos equivalentes a los números complejos . [2] ( Eric Bach señala que esta equivalencia puede verse como una forma del principio de Lefschetz .) [4]
La segunda parte se centra en los 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 las raíces de los polinomios y los puntos de intersección de las curvas algebraicas , el número de condición de los 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 de la teoría de la complejidad descriptiva para el cálculo de números reales, incluidas 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 siguen sin demostrarse. Una herramienta clave en esta área es el uso del número de componentes conectados de un conjunto semialgebraico para proporcionar un límite inferior a la complejidad temporal de un problema computacional asociado. [2]
El libro está dirigido al nivel de un estudiante de posgrado o investigador en estos temas, [2] [3] y en algunos lugares asume conocimientos básicos de la teoría clásica de la complejidad computacional, la geometría diferencial , la topología y los sistemas dinámicos . [3] [4]
El crítico Klaus Meer escribe que el libro está "muy bien escrito", "perfecto para usar en un nivel de posgrado" y representa bien tanto el estado del arte en esta área como las fuertes conexiones que se pueden hacer entre campos tan diversos como la teoría de números algebraicos , 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 lo que ocurre con las máquinas de Turing) los detalles aparentemente menores del modelo, como la capacidad de calcular las funciones de suelo y techo , pueden marcar grandes diferencias en lo que se puede calcular y en la eficiencia con la que se puede calcular. Sin embargo, Vavasis escribe que "esta dificultad es probablemente inherente al tema". [3] En relación con esto, Eric Bach se queja de que asignar un coste unitario a todas las operaciones aritméticas puede dar una idea errónea de la complejidad de un problema en el cálculo práctico, [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 claramente escrito de la teoría de la computación numérica. [3]