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 Blum-Shub-Smale como modelo de cálculo . Por ejemplo, esta teoría es capaz de abordar una pregunta planteada en 1991 por Roger Penrose en The Emperor's New Mind : "¿escomputable el conjunto de Mandelbrot ?" [1]
El libro fue escrito por Lenore Blum , Felipe Cucker , Michael Shub y Stephen Smale , con 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: aunque los científicos informáticos teóricos que trabajan en algoritmos discretos habían 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 habían fracasado en su mayor parte. para definir su modelo de cálculo, dejando sus resultados sobre una base inestable. Más allá del objetivo de fundamentar mejor este aspecto del tema, el libro también tiene el objetivo de presentar nuevos resultados en la teoría de la complejidad del cálculo de números reales y de recopilar resultados previamente conocidos en esta teoría. [3]
La introducción del libro reimprime el artículo "Complejidad y computación real: un manifiesto", publicado anteriormente 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 , lo que motiva el modelo más nuevo que se estudia 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 demuestra la existencia de problemas NP-completos de manera análoga a la demostración 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 campos algebraicamente cerrados de característicacero, que se muestran desde el punto de vista de la completitud de NP dentro de sus modelos computacionales para ser 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 Parte II 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 encontrar las 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]