Page 16 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

16

COMPLEJIDAD ALGORÍTMICA

Después de que la teoría de la computabilidad fuera desarrollada, era natural preguntarse acerca
de la dificultad computacional de las funciones computables. Este es el objetivo de la parte de las
ciencias de la computación que se conoce como complejidad algorítmica. Rabin fue uno de los
primeros en plantear esta cuestión general explícitamente: ¿Qué quiere decir que una función f
sea más difícil de computar que otra función g? Rabin sugirió una axiomática que fue la base
para el desarrollo del estudio de medidas de complejidad abstracta de Blum y otros (1967).

Una segunda aportación que tuvo una influencia relevante en el desarrollo posterior de esta
materia fue el artículo de J. Hartmanis y R. Stearns en 1965, cuyo título “On the complexity of
algorithms” dio nombre a este cuerpo de conocimiento. En él se introduce la noción fundamental
de medida de complejidad definida como el tiempo de computación sobre una Máquina de Turing
multicinta y se demuestran los teoremas de jerarquía.

Un tercer hito en los comienzos del tema fue el trabajo de Cobham titulado, “The intrinsic
computational difficulty of functions” (1964). Cobham enfatizó el término “intrínseco”, es decir,
él estaba interesado en una teoría independiente de las máquinas. Esto nos conduce a un concepto
importante desarrollado en 1965: la identificación de la clase de problemas que se pueden resolver
en tiempo acotado por un polinomio sobre la longitud de la entrada.

La distinción entre algoritmos de tiempo polinomial y algoritmos de tiempo exponencial fue
hecha por primera vez en 1953 por Von Neumann. La notación de p para la clase de los problemas
resolubles en tiempo polinomial fue introducida posteriormente por Karp (1972).

La teoría de la np-completitud es seguramente el desarrollo más importante de la complejidad
algorítmica. La clase np consta de todos los problemas decidibles en tiempo polinomial por una
Máquina de Turing no determinista.

Cook en 1971 introduce la noción de problema np-completo y demuestra que el problema de la
satisfacibilidad booleana es np-completo. La clase np incluye una gran cantidad de problemas
prácticos que aparecen en la actividad empresarial e industrial.

Demostrar que un problema es np-completo equivale a demostrar que no tiene una solución
determinista en tiempo polinomial, salvo que todos los problemas de np estén en p, cuestión que
aún no está demostrada.

Otra área que actualmente está teniendo cada vez más importancia es la criptografía, relacionada
con la seguridad de los sistemas informáticos y donde se ha aplicado especialmente la teoría de
la complejidad algorítmica. Mediante la criptografía podemos conseguir el manejo de
información confidencial en el ordenador de forma más o menos segura.