¿Complejidad del problema SAT

8

Definamos el problema SAT de : dado F 3 , una fórmula satisfactoria de 3-CNF, y F 2 , una fórmula de 2-CNF ( F 3 y F 2 se definen en las mismas variables). ¿Es F 3F 2 satisfactoria?(3,2)sF3F2F3F2F3F2

¿Cuál es la complejidad de este problema? (¿Ha sido estudiado antes?)

Xavier Labouze
fuente

Respuestas:

13

Este problema es NP-completo.

Sea una fórmula CNF arbitraria (una instancia de SAT). Considere φ y , donde y es una variable nueva; obviamente, esta fórmula es satisfactoria (simplemente puede establecer y en verdadero). Ahora convierta φ y a 3-CNF, utilizando cualquier método estándar, y deje que ote denote el resultado. Tenga en cuenta que ψ es una fórmula satisfactoria de 3-CNF, por lo que podemos dejar que F 3 = ψ . Ahora, dejemos F 2 = ¬ y . Tenga en cuenta que F 3F 2 es satisfactoria si y solo siφφyyyφyψψF3=ψF2=¬yF3F2 es. Por lo tanto, elproblema SAT ( 3 , 2 ) s es al menos tan difícil como el SAT. Además, claramente no es más difícil que el SAT. Por lo tanto, es exactamente tan difícil como el SAT.φ(3,2)s

DW
fuente
Tks @DW, bastante convincente.
Xavier Labouze
Solo debe reducir de 3SAT en lugar de SAT.
Tyson Williams
55
φφy
Ah, sí. Buen punto.
Tyson Williams
2

F3F3F2

Xavier Labouze
fuente