Prueba de DOBLE SAT es NP-completo

13

El conocido problema SAT se define aquí como referencia.

El problema DOUBLE-SAT se define como

DOUBLE-SAT={ϕϕ has at least two satisfying assignments}

¿Cómo demostramos que es NP-completo?

Se apreciará más de una forma de demostrar.

pnp
fuente

Respuestas:

26

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 ) ϕNPϕ(x1,,xn)ϕ

Para mostrar que Double-SAT es -Complete, ofrecemos una reducción de SAT a Double-SAT, de la siguiente manera:NP

En la entrada :ϕ(x1,,xn)

  1. Introducir una nueva variable .y
  2. Fórmula de salida .ϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯)

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 ϕ(x1,,xn)ϕϕ(x1,,xn,y)yy¯y=1y=0yϕx1xny

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ϕ(x1,,xn)SATϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯)ϕ(x1,,xn,y)Double-SAT

Por lo tanto, , y por lo tanto Double-SAT es -Complete.N PSATpDouble-SATNP

pnp
fuente
Eso es mejor que mi propuesta.
Raphael
10

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 TSATSATDOUBLE-SAT

Para cualquier fórmula , la fórmula tiene al menos el doble del número de asignaciones satisfactorias que , con un homomorfismo que cambia el nombre de todas las variables a nuevos nombres.φ f ( φ ) φ fφφf(φ)φf

Rafael
fuente