Una variante de SAT crítico en DP

10

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 2LDPL1NPL2coNPL=L1L2

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?DPFGFG

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?DPFF

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.FFFFNPcoNP

Mi pregunta: ¿esta variante DP-complete?

Gracias por sus respuestas.

Xavier Labouze
fuente
No estaba al tanto de DP: clase interesante, especialmente si CRITICAL-SAT está completa para ello.
Suresh Venkat
1
Si hay dos asignaciones satisfactorias , entonces φ no es máximo. (suponga que difieren en la variable pττφφp , entonces no está implícito en la fórmula y agregarlo o una cláusula que lo contenga no cambiará la satisfacción). Si podemos encontrar una cláusula no implicada por la fórmula en el tiempo polinómico, podemos agregar que es negación a la fórmula y simplemente usando la regla de la cláusula unitaria. Eventualmente encontraremos el valor de todas las variables para una asignación satisfactoria. Entonces solo necesitamos verificar si la fórmula es equivalente a la fórmula canónica para esa asignación. p
Kaveh
1
@Kaveh: no entendí su pregunta refinada. En su versión de la pregunta, "no hay una cláusula que no esté implícita en la fórmula y se pueda agregar sin hacerla insatisfactoria" es equivalente a la condición de que exista exactamente una asignación satisfactoria, y es un estándar de EE . UU . problema completo (de ahí coNP-hard).
Tsuyoshi Ito
1
Xavier: Tienes razón en que el idioma en la versión de @ Kaveh es un subconjunto del idioma en tu versión. Pero eso no implica reducibilidad entre los dos problemas (en cualquier dirección). Recuerde que una reducción debe asignar sí-instancias a sí-instancias y no-instancias a no-instancias.
Tsuyoshi Ito
1
Lo siento, escribí en la dirección opuesta. El idioma en su versión es un subconjunto del idioma en la versión de Kaveh.
Tsuyoshi Ito

Respuestas:

2

[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 :FcF 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 1l 2l 3F , donde l i es un literal. Como F { c } es UNSAT, todos los modelos de = 0 (para iFLFSATcFF{c}UNSATc=l1l2l3FliF{c} deben tener l iFli=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 1l . Entonces, por el mismo argumento, todos los modelos de F deben tener l 1 =i=1,2,3l1=1cF{c}cccFc=¬l1l2l3F . 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=1FLcFFcF FF choque, que claramente se puede hacer en tiempo lineal.

Anton Belov
fuente
1
Su observación es básicamente: para tener la respuesta Sí, F debe contener exactamente siete de las ocho cláusulas en cualquier elección de tres variables distintas. Por lo tanto, encontrar la asignación única (o detectar inconsistencias) se realiza fácilmente en tiempo polinómico.
Tsuyoshi Ito
2
@Xavier: Los dos problemas pueden parecer similares, pero la observación de Anton muestra que son simplemente muy diferentes. Esto es muy común en la complejidad computacional. Los ejemplos típicos incluyen la comparación entre 2SAT y 3SAT y entre el circuito de Eulerian y el circuito de Hamilton.
Tsuyoshi Ito
2
@Xavier: la respuesta de Tayfun es incorrecta . Él muestra que el problema está en DP: está bien, cualquier problema en P está automáticamente en DP. Para demostrar que el problema es DP completo, debe mostrar la reducción a otro problema DP completo (por ejemplo, la primera variante de SAT crítico). Envié la edición a su respuesta, pero está en la cola para "revisión por pares".
Anton Belov
3
@Anton: por lo general, no se recomienda editar drásticamente las respuestas publicadas por otros usuarios. Si crees que la respuesta de Tayfun es fundamentalmente incorrecta, no debes tratar de solucionarlo editándolo.
Tsuyoshi Ito
1
Del problema SAT-UNSAT queda muy claro que para una fórmula se verifica la satisfacción de la otra fórmula se verifica si no es satisfactoria ... En el problema crítico crítico original no se da por sentado que la fórmula booleana dada no es satisfactoria. Tienes que comprobarlo. Lo mismo con la versión de Xaviers, debe verificar que la fórmula booleana dada sea satisfactoria.
Tayfun paga el
-1

¿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 FFFF hace insatisfactorio?

Y "Problema 2": dada una expresión 3 CNF , ¿es cierto que FFF 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. FFFFFFF 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. » FFFFFFFFFF 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.FF

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(n1)(n2)3n

Xavier Labouze
fuente
2
Reescribió el problema original a su gusto.
Tayfun Pay
No estoy seguro acerca de la versión 3-SAT. Dada una fórmula booleana en CNF con cláusulas M y variable N, SI M = (3 ^ N) - (2 ^ N), entonces la fórmula booleana dada es INSATISFIABLE o solo tiene UNA solución. Aun así, verificar la satisfacción en esa instancia sigue siendo NP. No hay forma de que su versión esté en P.
Tayfun Pay
1
@Xavier: Esta respuesta parece correcta, pero creo que es lo mismo que Anton hace en su respuesta.
Tsuyoshi Ito
@ Tsuyoshi, tienes razón, solo presentamos el problema 2 cuya primera parte (probar si una fórmula contiene todas las cláusulas que implica) me interesa, por cierto, ¿tienes alguna idea sobre la complejidad de esta primera parte?
Xavier Labouze