Doble SAT es NP Completo

Declaración del problema : dada una fórmula f , el problema es determinar si f tiene dos asignaciones satisfactorias.

Explicación : una instancia del problema es una entrada especificada para el problema. Una instancia del problema Double Sat es una fórmula booleana f . Dado que un problema NP-completo es un problema que es tanto NP como NP-Difícil , la prueba o afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso.
   (B es reducible en tiempo polinomial a C se denota como B ≤ P ^C )

Si solo se cumple la segunda condición, el problema se llama NP-Hard .
Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Por lo tanto, para mostrar que un problema es NP-completo, luego demuestre que el problema está en NP y cualquier problema NP-Completo es reducible a eso, es decir, si B es NP-Completo y B ≤ P ^C . Por lo tanto, se puede verificar que el problema Doble SAT es NP-Completo usando las siguientes proposiciones:

1. Double Sat está en NP :
   si algún problema está en NP, entonces se le da un ‘certificado’, que es una solución al problema y una instancia del problema (una fórmula f ) y luego puede identificar (si la solución es correcta o no) certificado en tiempo polinomial. Esto se puede hacer dando un conjunto de asignaciones satisfactorias para las variables en f , y verificando si cada cláusula se cumple en f .
2. Double Sat es NP-Hard :
   para probar que Double Sat es NP-Hard, reduzca un problema NP-Hard conocido, 3-SAT (en este caso) a nuestro problema.
   Esto se puede hacer:
   Dada una función 3-CNF g , cree una función booleana f agregando un par de literales (x V x’) a cada cláusula de f , donde x es una variable adicional. Esta reducción puede funcionar en tiempo polinomial.
   Ahora bien, se cumplen las siguientes dos proposiciones:
   • Si g es insatisfactoria, entonces alguna cláusula de g debe ser FALSA y, por lo tanto, f también debe ser insatisfactoria.
   • Si la fórmula g de 3-SAT es satisfactoria, entonces usando el mismo conjunto de variables de asignación comprendidas en g , podemos tener tanto x=0 como x=1 como las asignaciones válidas para g .

Por lo tanto, el Problema de Doble SAT es NP-Completo.