Introducción a la Teoría de la Complejidad Computacional

Abstract

Esre Trabajo de Fin de Grado consiste en una introducción a la Teoría de la Complejidad Computacional de Tiempo, para lo cual se comienza definiendo la máquina de Turing como modelo computacional básico, antes de adentrarnos en las diferentes clases de complejidad tanto deterministas como indeterministas, haciendo una revisión más profunda de las clases P y NP como protagonistas de esta área. Se estudian las reducciones, herramientas fundamentales en el manejo de las clases de complejidad, y la NP-completitud como consecuencia directa de lo anterior. Como colofón, se termina con un capítulo dedicado en exclusiva la famosa Conjetura de Cook, uno de los problemas del milenio. Debido a su utilidad como referencia inicial en Complejidad Computacional, la selección de resultados y demostraciones pretende además familiarizar al lector con las técnicas propias de esta rama de las Matemáticas.