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.
Full text
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 teoremas de Goedel, de Cook, y otros teoremas clasicos desde un nuevo punto de vista.