Problema de satisfacibilidad booleana

Keywords: Problema de satisfacibilidad booleana, Clase de complejidad, Complejidad computacional, NP-completo, Wikipedia

En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP-completo

Se trata de un problema donde interesa saber si una expresión booleana con variables y sin cuantificadores tiene asociada una asignación de valores para sus variables que hace que la expresión sea verdadera. Por ejemplo, una instancia de SAT sería el saber si existen valores para $x_1,\, x_2, \, x_3, \, x_4$ tales que la expresión

$(x_1 \or \neg x_3 \or x_4) \and (\neg x_2 \or x_3 \or \neg x_4)$

es cierta.

WikiLetra

Este artículo es, por ahora, sólo un esbozo. Ampliándolo ayudarás a mejorar Wikipedia. Puedes encontrar fuentes en las wikipedias en otras lenguas. Si lo amplias hasta el punto de que este cartel no sea necesario por favor, elimínalo.