El isomorfismo de Curry Howard establece una sorprendente correspondencia entre sistemas de lógica formal y cálculos computacionales. El isomorfismo adquiere distintas formas: las fórmulas se corresponden a tipos, las pruebas se corresponden a programas, la existencia de una prueba se…
Miguel Campercholi, 2019-09-11: “Introducción a la Complejidad Computacional” (Segunda Parte)
En esta charla discutiremos los conceptos e ideas básicas de la Complejidad Computacional. Daremos las definiciones de las clases P y NP, las diferentes nociones de reducción entre problemas computacionales, y el concepto de problema NP-completo. (source)
Miguel Campercholi, 2019-09-04: “Introducción a la Complejidad Computacional”
En esta charla discutiremos los conceptos e ideas básicas de la Complejidad Computacional. Daremos las definiciones de las clases P y NP, las diferentes nociones de reducción entre problemas computacionales, y el concepto de problema NP-completo. (source)