Panorámica de la teoría computacional: desarrollo y problemas abiertos

Abstract

[ES] En este trabajo se exponen sendas introducciones a los conceptos propios de la teoría de la computación y de la teoría de la complejidad computacional, prestando especial atención a los movimientos filosóficos que propiciaron su desarrollo. Asimismo, se presenta una de las incógnitas sin resolver más importantes de laMatemática, la conjetura de Cook, así como sus consiguientes implicaciones al respecto de la naturaleza de los propios problemas.

[EN] This dissertation, two introductions are presented to the concepts of computational theory and the computational complexity theory paying special attention to the philosophical movements that led up to its development. Also presents one of the most important unresolved unknows of Mathematics, the Cook’s conjecture, as well as its consequent implications for the nature of the problems themselves.