Horario: 9 a 12 hs.
Un caso especial en esta área es aquel en el que R=R. Aquí, los supuestos de que todos los elementos del anillo tienen tamaño unidad y que el costo de las operaciones aritméticas es también unitario, refleja las características de los algoritmos del Análisis Numérico o de la Geometría Computacional. Recientemente, un artículo de Lenore Blum, Michael Shub y Steve Smale introdujo en este escenario otro punto de vista en complejidad: el estructural (ver [1]). Para ello, idearon un modelo de máquina de Turing real sobre el cual se construyen las bases de una teoría de la calculabilidad y la complejidad sobre los reales. En particular, se introducen las clases PR y NPR, análogas a las conocidas P y NP y se demuestra que el problema de decidir cuando un polinomio a coeficientes reales de grado 4 tiene una raíz real, es NPR completo para reducciones en PR.
El curso se basará en el libro de Lenore Blum, Juan Cucker, Michael Shub y Steve Smale que contiene una exposición sistemática de la teoría de complejidad sobre los reales así como una serie de algoritmos de análisis numérico y un análisis detallado de su complejidad en función de algunos parámetros geométricos (números de condición).
Referencias:
[1] L. Blum, M. Shub y S. Smale; “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines”. Bulletin of the Amer. Math. Soc., vol. 21, n.1, pp.1-46, 1989.
[2] J. von zur Gathen; “Algebraic complexity theory”, Ann. Rev. Comput. Sci., 3, pp.317-347, 1988.
Este curso se dictará en español.