problema sat

¿Qué es SAT?
El problema SAT se puede enunciar como sigue: dada una fórmula proposicional en
forma normal conjuntiva, determinar si esta es satisfactible.
Así, el problema consiste en decidir, dada una FNC F, si existe alguna valoración de
verdad 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, esdecir, 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.

¿Es computable el problema SAT?
Sí, existen algoritmos correctos y completos que resuelven SAT. El problema de estos
algoritmos es su ineficienciapráctica. Un ejemplo de algoritmo correcto y completo que
resuelve SAT es el de tablas de verdad.
Resolver SAT con tablas de verdad consiste en generar todas las posibles valoraciones
de verdad de las variables de la fórmula, viendo si para alguna de ellas la fórmula se
hace cierta. Obviamente este algoritmo es exponencial en tiempo (2 elevado al número
de variables), por lo que en la práctica esinabordable para un número suficientemente
grande de variables.
Así pues, el problema real es obtener un algoritmo eficiente para determinar la
satisfactibilidad de una fórmula. Este se trata de un problema abierto del que se postula
que tendrá respuesta negativa (no se han dado algoritmos polinomiales, correctos y
completos y además implicaría P=NP).
Aún así, existen algoritmos que son muyeficientes para un tipo concreto de fórmulas, y
en muchas ocasiones esto es suficiente para ciertos propósitos prácticos.

Variantes del problema SAT
Existen multitud de variantes del problema SAT, estos problemas surgen de imponer
restricciones a la fórmula en FNC de la que se partía inicialmente.
Además, todos los problemas NP son reducibles en tiempo polinomial a SAT, ya que esNP-Completo. Esto quiere decir que existe un algoritmo que transforma una instancia
del problema en SAT o viceversa y además ese algoritmo es polinomial.
Estos problemas, tanto las variantes de SAT como los reducibles a SAT en tiempo
polinomial, se pueden considerar equivalentes a SAT en el sentido de que un algoritmo
que trabaje eficientemente para SAT resolvería cualquiera de los problemas tambiéneficientemente.
Así, es de vital interés la resolución del problema SAT de forma eficiente ya que a su
vez estaríamos resolviendo con la misma eficiencia todos los problemas NP.

Algunos de las variantes y problemas equivalentes a SAT son las siguientes:









SAT(k) – Dada una fórmula en FNC con a lo sumo k literales por cláusula,
determinar si esta es satisfactible.SAT*(k) – Dada una fórmula en FNC con exactamente k literales por
cláusula, determinar si esa es satisfactible.
SAT(3) – Dada una fórmula en FNC con a lo sumo 3 literales por cláusula,
determinar si esta es satisfactible.
Vertex Cover – Dado un grafo G y un número natural k, determinar si hay un
recubrimiento de vértices de G de tamaño k.
SUBSET-SUM – Dado un conjunto A, una función de peso w yun número
natural k, determinar si existe un subconjunto B de A tal que w(B) = A.
PARTICIÓN – Dado un conjunto A y una función de peso w, determinar si
existe una partición de A {B,C} tal que w(B) = w(C).
3-COL – Determinar si un grafo es 3-coloreable.
HAM-PATH – Dado un grafo G y dos nodos x e y pertenecientes a G,
determinar si existe un camino Hamiltoniano de x a y.

Estos son soloalgunos ejemplos de problemas equivalentes a SAT. Existen multitud de
más problemas interesantes reducibles en tiempo polinomial al problema de
satisfactibilidad, como el problema del viajante de comercio por citar otro ejemplo.
Esto hace que SAT tenga infinidad de utilidades practicas en diversos campos como
matemáticas, inteligencia artificial o robótica.

Algoritmos de resolución
Como se...