Complejidad y computabilidad desde un punto de vista lógico

Abstract

En esta charla trataremos temas clasicos de complejidad y computabilidad visto desde un punto de vista lógico. En particular, veremos como a cada clase de complejidad corresponde, en general, un problema de satisfiactibilidad de fórmulas de un lenguaje lógico concreto, mostrando así como la jerarquía computacional es, en efecto, una jerarquía lógica. Trataremos entonces los teorema de Goedel, de Cook, y otros teoremas clasicos desde un nuevo punto de vista.