Computabilidad y complejidad computacional

Abstract

Se describen, de manera introductoria y sistemática, elementos clásicos de la teoría de la computabilidad y la teoría de la complejidad computacional, las cuales estudian, respectivamente, los límites de lo computable (qué problemas se pueden resolver considerando un modelo computacional universal) y el costo computacional de las resoluciones de los problemas que efectivamente se pueden resolver. El modelo utilizado lo constituyen las máquinas de Turing, y el costo computacional se establece en términos del tiempo (cantidad de pasos) y el espacio (cantidad de celdas) de dichas máquinas.