Logica Matematica

PROBLEMA DE LA SATISFACTIBILIDAD (SAT)

El problema SAT se puede enunciar como sigue: dada una fórmula proposicional enforma normal conjuntiva, determinar si esta es satisfactible.

Así, el problema consiste en decidir, dada una FNC F, si existe alguna valoración deverdad V sobre el conjunto de variables de la fórmula tal que V(F) = 1.

Una de las características mas importantes del problema es que es NP-Completo, es decir, el tiempo de ejecución para un algoritmo que resuelva el problema es exponencial en el número de cláusulas de la fórmula. Este resultado fue demostrado por S.A. Cook en 1971, dando lugar al nacimiento de la teoría de la complejidad.