SAT (satisfacilidad)

 

El problema SAT o también llamado satisfacibilidad booleana es un problema donde queremos saber si un problema con variables y sin cuantificadores tiene una asignación para sus variables que hace que aquella expresión sea verdadera. Por ejemplo una instancia SAT sería saber si  existen valores para                                 que la expresión:

  Es cierta.

 

 Ahora si bien un problema es satisfacible si existe al menos una asignación de valores a las variables del problema que lo hagan verdadero () Y un problema es insatisfacible si todas las posibles asignaciones de valores hacen el problema siempre falso ().