El conocido problema SAT se define aquí como referencia.
El problema DOUBLE-SAT se define como
¿Cómo demostramos que es NP-completo?
Se apreciará más de una forma de demostrar.
El conocido problema SAT se define aquí como referencia.
El problema DOUBLE-SAT se define como
¿Cómo demostramos que es NP-completo?
Se apreciará más de una forma de demostrar.
Aquí hay una solución:
Claramente Double-SAT pertenece a , ya que un NTM puede decidir Double-SAT de la siguiente manera: en una fórmula de entrada booleana , adivina de manera no determinista 2 asignaciones y verifica si ambas satisfacen . ϕ ( x 1 , … , x n ) ϕ
Para mostrar que Double-SAT es -Complete, ofrecemos una reducción de SAT a Double-SAT, de la siguiente manera:
En la entrada :
Si pertenece a SAT, entonces tiene al menos 1 tarea satisfactoria y, por lo tanto, tiene al menos 2 tareas satisfactorias como podemos satisfacer la nueva cláusula ( ) asignando o a la nueva variable , entonces ( , ..., , ) Double-SAT.ϕ ϕ ′ ( x 1 , … , x n , y ) y ∨ ˉ y y = 1 y = 0 y ϕ ′ x 1 x n y ∈
Por otro lado, si , entonces claramente tampoco tiene una asignación satisfactoria, entonces .ϕ ′ ( x 1 , ... , x n , y ) = ϕ ( x 1 , ... , x n ) ∧ ( y ∨ ˉ y ) ϕ ′ ( x 1 , ... , x n , y ) ∉ Doble SAT
Por lo tanto, , y por lo tanto Double-SAT es -Complete.N P
Usted sabe que es NP-complete. ¿Puedes encontrar una reducción de a ? Es decir, ¿puede manipular una fórmula satisfactoria para que el resultado tenga al menos dos tareas satisfactorias? Tenga en cuenta que la misma manipulación no puede hacer que las fórmulas insatisfactorias sean satisfactorias.S A T D O U B L E - S A TSAT SAT DOUBLE-SAT
fuente