Modelado del 3-coloreo de grafos planares usando satisfactibilidad Incremental
No Thumbnail Available
Date
2021-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
"Uno de los problemas fundamentales en el razonamiento automático es el problema de
satisfactibilidad proposicional (SAT), el SAT es un problema de la clase de complejidad NP-Completo. Las aplicaciones de SAT rara vez se limitan a resolver sólo una fórmula de entrada, una aplicación normalmente resolverá una secuencia de fórmulas relacionadas.En esta investigación se propone una estrategia para utilizar estructuras que se formen en la fase 1 de 2-ISAT y que sean usadas durante la fase 2 del problema. Se propone revisar si pueden haber estructuras computacionales que creadas en la primer fase, resuelvan 2-ISAT en tiempo polinomial, o bien, el problema 2-ISAT es de complejidad
NP."