¿El SAT 1 en 3 permanece NP-duro incluso si todas las variables ocurren tanto positiva como negativamente?

El problema estándar 1-en-3 SAT (o XSAT o X3SAT) es:
Instancia : una fórmula CNF con cada cláusula que contiene exactamente 3 literales
Pregunta : ¿existe una asignación satisfactoria que establezca exactamente 1 literal por cláusula verdadera?

El problema es NP-completo y sigue siendo difícil incluso si no se produce una variable negada. Me pregunto si este problema se vuelve fácil o difícil si se requiere que cada variable ocurra al menos una vez de manera positiva y al menos una vez de manera negativa .

La reducción habitual de 3SAT que muestra que 1-en-3 SAT es difícil reemplaza una cláusula por cláusulas , , donde son frescas para cada cláusula. Por lo tanto, esta reducción no ayuda a responder mi pregunta. He tenido problemas para encontrar un dispositivo que muestre la dureza de esta variante, ya que si exactamente 1 literal en una cláusula es verdadero, entonces los 2 literales no simétricos son falsos. Si resulta fácil, pensar en términos de particiones del conjunto de cláusulas podría hacerlo, pero no puedo ver cómo. $(x\lor y \lor z)$ $(\lnot x \lor a \lor b)$ $(y\lor b\lor c)$ $(\lnot z \lor c \lor d)$ $a,b,c,d$

cc.complexity-theory np-hardness sat Dominik Peters
fuente

¿Se puede reducir a 2 sat?

Joshua Herman

pista: para cada var , agregue cláusulas y, diga, .

X_{i}

$X_i$

(X_{i} \lor {\bar{X}}_{i} \lor W) \land (X_{i} \lor {\bar{X}}_{i} \lor Y) \land (X_{i} \lor {\bar{X}}_{i} \lor Z)

$(X_i\vee \overline X_i \vee W) \wedge (X_i\vee \overline X_i \vee Y)\wedge (X_i\vee \overline X_i \vee Z)$

(W \lor Y \lor \bar{Z})

$(W \vee Y \vee \overline Z)$

Neal Young

Ja, eso funciona (por supuesto, agregando también ). Dejaré la pregunta abierta en caso de que alguien pueda resolverlo sin el truco .

(\bar{W} \lor Y \lor Z) \land (W \lor \bar{Y} \lor Z)

$(\overline W \lor Y\lor Z)\land(W\lor\overline Y \lor Z)$

X_{i} \lor {\bar{X}}_{i}

$X_i\lor\overline X_i$

Dominik Peters

¿Puedo animarlo a escribir una respuesta completa a su propia pregunta, tal vez basada en la idea de Neal young? (Por cierto, no estoy seguro de por qué eso es "insatisfactorio". Una reducción es una reducción).

Si ese caso especial es el que realmente le importa, ¿entonces quizás tenga sentido editar su pregunta para reflejar esa restricción adicional?

Respuestas:

En un comentario, OP expresó interés en una reducción que generó instancias con 3 variables distintas por cláusula. Aquí hay un enfoque simple:

La reducción es de 1 en 3 SAT con 3 variables distintas por cláusula:

En primer lugar, incluya todas las cláusulas en la fórmula de entrada como cláusulas en la fórmula de salida.
En segundo lugar, introduzca tres nuevas variables , y y agregue las siguientes tres cláusulas a la fórmula de salida: , y . $F_1$ $F_2$ $F_3$ $(\neg F_1, F_2, F_3)$ $(F_1, \neg F_2, F_3)$ $(F_1, F_2, \neg F_3)$
Finalmente, para cada variable en la fórmula original, introduzca una nueva variable y agregue las siguientes dos cláusulas a la fórmula de salida: y . $x$ $x'$ $(x, x', F_1)$ $(\neg x, \neg x', F_1)$

Verifiquemos que esta reducción haga lo que queremos. Las siguientes propiedades son lo que queremos:

Cada cláusula siempre tiene tres variables distintas.
Cada variable ocurre en alguna cláusula positivamente y en alguna cláusula negativamente.
La fórmula de entrada es equivalente a la fórmula de salida.

La propiedad 1 es trivial para verificar. La propiedad 2 también es fácil de verificar: las variables , y presentan de manera positiva y negativa en las cláusulas agregadas en el segundo punto, mientras que todas las demás variables en la fórmula se presentan de manera positiva y negativa en las cláusulas agregadas en Tercera viñeta. $F_1$ $F_2$ $F_3$

En cuanto a la propiedad 3, esto es menos trivial pero aún así fácil. Puede argumentar fácilmente que la única asignación para las variables , y que satisface cada cláusula desde el segundo punto es hacer que las tres falsas. Pero luego, suponiendo un valor de falso para , las cláusulas y agregadas en el tercer punto se satisfacen si y solo si . Como no hay otras restricciones en , esto significa que siempre es posible extender una asignación satisfactoria para la fórmula de entrada en una asignación satisfactoria para la fórmula de salida: simplemente configure cada $F_1$ $F_2$ $F_3$ $F_i$ $F_1$ $(x, x', F_1)$ $(\neg x, \neg x', F_1)$ $x' = \neg x$ $x'$ $x'$ será la negación de la correspondiente y establecerá cada en falso. $x$ $F_i$

Mikhail Rudoy
fuente