Después que la teoría de computabilidad fue desarrollada se comenzó analizar la complejidad de los algoritmos. En 1960 Rabin fue el primer hombre en plantear en forma explicita cual es la complejidad computacional. Rabin sugirió el axioma que fue la base para el desarrollo de la teoría de la complejidad abstracta de blum y otros.
Una pequeña aportación (1965) aparecía en el articulo J. Hartmanis and R.E. stearns on the computacional complexity of algorithms. En este introduce la noción fundamental de medida de complejidad la cual queda definida como el tiempo de computación sobre de una maquina de Turing multicinta.
Se puede computar cualquier número irreal algebraico en tiempo real del número a una velocidad de un digito cada 100 paso.
Posteriormente Cobham publico un articulo the intrinsic computacional difficulty or funtion enfatizo el termino intrínseco es decir el estaba interesado en una teoría innovadora de maquinas. Se pregunto si la multiplicación es más compleja que la suma y considero que la pregunta podía ser contestada hasta que se desarrollaba la teoría.
También definió y caracterizo la importante de las clases de funciones llamadas función es de números naturales que son computables en tiempo contando por un polinomio cuyo argumento es longitud de entrada.
No hay comentarios:
Publicar un comentario