El Problema del Milenio PvsNP: Introducción a la NP-Completitud

Abstract

La Teor´ıa de la Complejidad Computacional es una rama de las ciencias de la computaci´on que estudia la clasificaci´on de problemas en funci´on de los recursos requeridos para resolverlos (tiempo y espacio). Entre los problemas m´as estudiados en este campo se encuentra uno de los Siete Problemas del Milenio propuestos por la fundaci´on Clay Mathematics Institute de Cambridge, el Problema “P vs NP”, siendo uno de los m´as importantes no s´olo en este ´ambito, sino dentro de las matem´aticas en general. En este Trabajo Fin de Grado se introducir´a al problema y uno de los grandes caminos para atacarlo: la Teor´ıa de la NP-completitud, exponiendo sus problemas cl´asicos y m´etodos asociados. Para concluir, se har´a una reflexi´on de c´omo aplicar dicha teor´ıa y la implicaciones en la sociedad de sus posibles respuestas.

Computational Complexity Theory is a branch of computer science that studies the problems classification according to the resources required to solve them (time and space). Among the main problems studied in this field we find one of the Seven Millennium Problems proposed by the Clay Mathematics Institute of Cambridge, the Problem “P vs NP”, being one of the most important not only in this field, but also in mathematics in general. In this Final Degree Project we will introduce the problem and one of the main ways to attack it: the NP-completeness theory, exposing its classical problems and associated methods. Finally, a reflection will be made on how to apply this theory and the implications in society of its possible answers.