Introducción a la teoría de la complejidad computacional

Abstract

El objetivo de este trabajo de fin de grado es realizar un estudio de los principales conceptos de la teoría de la complejidad computacional. Se comenzará con un análisis de las maneras en las que se puede determinar el coste temporal de un algoritmo mediante el uso de máquinas de Turing de diferentes tipos. Estos conceptos se usarán para definir las clases P y NP y estudiar su relación a través de los problemas NP-duros y NP-completos. Para ello, se utilizará la técnica de la reducción polinomial, que se ejemplificará con algunos de los casos más destacados de estos problemas (SAT, coloreado de grafos, búsqueda de caminos hamiltonianos...). Finalmente, se estudiarán algunas maneras de mitigar la dificultad de resolución de estos problemas, por ejemplo mediante algoritmos heurísticos y aproximados.