Problema de satisfacibilidad booleana
De Wikipedia, la enciclopedia libre
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 
tales que la expresión:
es cierta.
El problema sigue perteneciendo a la clase de complejidad NP-completo aunque se restrinja el número de literales por claúsula a un máximo de 3. En este caso se conoce como 3 SAT. Cuando el número máximo de literales por cláusula es dos, el problema tiene complejidad polinómica y se conoce como problema 2 SAT.
 |
El contenido de esta página es un esbozo sobre informática. Ampliándolo ayudarás a mejorar Wikipedia. Puedes ayudarte con las wikipedias en otras lenguas. |
