Un idioma está en la clase D P si hay dos idiomas L 1 ∈ N P y L 2 ∈ c o N P de modo que L = L 1 ∩ L 2
Un problema canónico completo de es SAT-UNSAT: dadas dos expresiones 3-CNF, F y G , ¿es cierto que F es satisfactoria y G no?
También se sabe que el problema crítico del SAT es -completo: dada una expresión 3-CNF F , ¿es cierto que F es insatisfactorio pero eliminar cualquier cláusula lo hace satisfactorio?
Estoy considerando la siguiente variante del problema crítico de SAT: Dada una expresión 3-CNF , ¿es cierto que F es satisfactoria pero agregar cualquier cláusula 3 (fuera de F pero usando las mismas variables que F ) lo hace insatisfactorio? Pero no logro encontrar una reducción de SAT-UNSAT o incluso probar que es N P o c o N P difícil.
Mi pregunta: ¿esta variante DP-complete?
Gracias por sus respuestas.
fuente
Respuestas:
[Lo convertí en una respuesta adecuada porque alguien me dio -1]
Si se permite agregar alguna cláusula, entonces el idioma está vacío; claramente a cualquier fórmula satisfactoria puede agregar una cláusula 3 c compuesta de variables que no aparecen en F :F c F será satisfactoria.F∪{c}
Si las cláusulas agregadas deben usar variables de , entonces el lenguaje está en P.F
La justificación es la siguiente:
Tome cualquier , es decir, F ∈ S A T y para cualquier 3-cláusula c en variables de F , F ∪ { c } ∈ U N S A T . Digamos c = l 1 ∨ l 2 ∨ l 3 ∉ F , donde l i es un literal. Como F ∪ { c } es UNSAT, todos los modelos de = 0 (para iF∈L F∈SAT c F F∪{c}∈UNSAT c=l1∨l2∨l3∉F li F∪{c} deben tener l iF li=0 ) - porque si algún modelo tuviera, por ejemplo, l 1 = 1 , entonces satisfaría c y entonces F ∪ { c } . Ahora, suponga que existe otra cláusula c ' que es exactamente como c , pero con uno o más literales invertidos y tal que c ′ ∉ F , digamos c ′ = ¬ l 1 ∨ l . Entonces, por el mismo argumento, todos los modelos de F deben tener l 1 =i=1,2,3 l1=1 c F∪{c} c′ c c′∉F c′=¬l1∨l2∨l3 F . Por lo tanto, la condición necesaria para F ∈ L es que para cada cláusula c ∈ F hay exactamente otros 6 cláusulas en F que utilizan las tres variables de c - le permite llamar a estos subconjuntos 7-cláusula de F bloques. Tenga en cuenta que cada bloque implica una asignación satisfactoria única a sus variables. Cuando se cumple esta condición necesaria, F es únicamente satisfactoria o insatisfactoria. Los dos casos se pueden distinguir probando si las asignaciones implicadas por los bloques de Fl1=1 F∈L c∈F F c F F F choque, que claramente se puede hacer en tiempo lineal.
fuente
¿Puedo proponer una respuesta a mi propia pregunta gracias a sus comentarios: la variante de Critical SAT está en P.
Llamemos al "Problema 1" la variante de SAT crítico: Dada una expresión 3-CNF , ¿es cierto que F es satisfactoria pero agregando cualquier cláusula de FF F F hace insatisfactorio?
Y "Problema 2": dada una expresión 3 CNF , ¿es cierto que FF F contiene todas las cláusulas que implica y tiene un modelo único?
Dada una fórmula 3-CNF,F .
Si es un ejemplo de sí problema 2, entonces cualquier cabo cláusula de F no está implicada por F y luego cubre el único posible asignación satisfactorio para F . Agregar tal cláusula a F hace que sea inviable. FF F F F F F es, en consecuencia, una instancia sí del problema 1.
Si es un ejemplo no de problema de 2, a continuación: Caso 1: existe una cláusula de F que está implicado por F . Luego, agregar esta cláusula a F no cambia su satisfacción. En consecuencia, F no es una instancia del problema 1. Caso 2: F contiene todas las cláusulas que implica pero es insatisfactorio. Por consiguiente, F no es una instancia del problema 1. Caso 3: F contiene todas las cláusulas que implica pero tiene al menos 2 modelos diferentes. Como subraya el comentario de Kaveh, «suponga que los modelos difieren en la variable p, luego agregar una cláusula que lo contenga no cambiará la satisfacción. » FF F F F F F F F F es, en consecuencia, una instancia del problema 1.
Entonces, es una instancia de sí del problema 1 si f es una instancia de sí del problema 2.F F
El problema 2 es claramente un problema P (por ejemplo, es una instancia sí del problema 2 si hay exactamente ( nF =n(n-1)(n-2)(n3) cláusulas de F sin literales opuestos en dos de ellas:nes el número de variables). Así es el problema 1.n(n−1)(n−2)3 n
fuente