Del problema SAT y la teoría de grafos

Ponente(s): Sonia Navarro Flores

El problema SAT consiste en decidir si cualquier fórmula booleana libre de cuantificadores es satisfactible o no. El primer resultado importante sobre este problema nos dice que es NP-completo, es decir, que cualquier problema NP se puede traducir a una subclase del problema SAT. Como este problema tiene diversas aplicaciones a la Inteligencia Artificial, dentro de las Ciencias Computacionales se han desarrollado métodos para buscar fragmentos de SAT que sean solubles en tiempo polinomial. En esta charla presentaremos una aproximación a este problema través de la teoría de grafos.