¿Es 2-SAT con relaciones XOR NP-completo?

11

Me pregunto si hay un algoritmo polinómico para "2-SAT con relaciones XOR". Tanto 2-SAT como XOR-SAT están en P, pero ¿es su combinación?

Entrada de ejemplo:

  • Parte 2-SAT: (a or !b) and (b or c) and (b or d)

  • Parte XOR: (a xor b xor c xor 1) and (b xor c xor d)

En otras palabras, la entrada es la siguiente fórmula booleana:

(a∨¬b)∧(b∨c)∧(b∨d)∧(a⊕b⊕¬c)∧(b⊕c⊕d).

Ejemplo de salida: Satisfacible: a = 1, b = 1, c = 0, d = 0.

Tanto el número de cláusulas 2-SAT como el número de cláusulas XOR en la entrada son , donde es el número de variables booleanas.nO(n)n

np-complete satisfiability xor 2-sat Albert Hendriks
fuente
1
este problema es bastante cercano, bitor xor de vectores para igualar un vector objetivo , cstheory.se
vzn

Respuestas:

11

Las relaciones 2-SAT-con-XOR pueden probarse NP-completo mediante la reducción de 3-SAT. Cualquier cláusula 3-SAT se puede reescribir en la expresión de relaciones 2-SAT-with-XOR equisatisfiable con y como nuevas variables.

(x1∨x2∨x3)
(x1∨y¯)∧(y⊕x2⊕z)∧(z¯∨x3)
yz
Kyle Jones
fuente
Todas las respuestas parecen ser correctas o de ayuda, pero esta me pareció la más elegante (en mi humilde opinión).
Albert Hendriks
1
Buena respuesta. Vale la pena mencionar que la mera satisfacción no sería suficiente aquí (ya que las asignaciones satisfactorias de las expresiones correspondientes a todas las cláusulas de un CNF satisfactorio podrían no coincidir), pero su expresión reescrita en realidad tiene una asignación satisfactoria correspondiente para cada asignación satisfactoria de La cláusula original.
Klaus Draeger
7

No ha especificado la aridad de sus relaciones XOR, pero como en la reducción habitual de SAT a 3SAT, siempre puede organizar que su aridad sea como máximo 3. Ahora está en una excelente posición para aplicar el teorema de dicotomía de Schaefer , que decirle si su problema está en P o NP-completo (estas son las dos únicas opciones). Si resulta que está en P, el siguiente paso podría ser mirar a Allender et al. , que le permitirá saber qué tan fácil es su problema.

Yuval Filmus
fuente
Esto no tiene en cuenta la condición de que haya restricciones , pero siempre puede agregar variables ficticias para asegurarse de que se cumple la condición. O(n)
Yuval Filmus
5

Según el teorema de la dicotomía de Schaefer , esto es NP completo.

Considere el caso donde todas las cláusulas tienen 2 o 3 literales en ellas; entonces podemos considerar esto como un problema de satisfacción de restricciones sobre un conjunto de relaciones de aridad 3. En particular, las relaciones son las siguientes: , , , , .ΓR(x,y,z)x∨yx∨¬y¬x∨¬yx⊕y⊕zx⊕y⊕¬z

Ahora aplique el teorema de dicotomía de Schaefer, en su forma moderna . Verifique cada una de las seis operaciones para ver si son un polimorfismo:

  • Unario 0: no es un polimorfismo de .x∨y
  • Unario 1: No es un polimorfismo de .¬x∨¬y
  • Binario AND: no es un polimorfismo de . (Considere y ; ambos satisfacen la relación, pero su Y-puntiagudo Y no.)x∨y(0,1,0)(1,0,0)(0,0,0)
  • Binario OR: no es un polimorfismo de . (Considere y ; satisfacen la relación, pero no.)¬x∨¬y(0,1,0)(1,0,0)(1,1,0)
  • Mayoría ternaria: no es un polimorfismo de . (Considere y y ; satisfacen la relación, pero su mayoría no.)x⊕y⊕z(0,0,1)(0,1,0)(1,0,0)(0,0,0)
  • Minoría ternaria: no es un polimorfismo de . (Considere , y ; satisfacen la relación, pero su minoría no.)( 0 , 1 , 0 ) ( 1 , 0 , 0 ) ( 1 , 1 , 0 ) ( 0 , 0 , 0 )x∨y(0,1,0)(1,0,0)(1,1,0)(0,0,0)

Se deduce que este problema es NP-completo, incluso si restringe todas las cláusulas XOR para que tengan una longitud máxima de 3.

Por otro lado, si todas las cláusulas XOR están restringidas a una longitud máxima de 2, entonces esto está en P. En particular es equivalente a , por lo que cualquier fórmula de este tipo es equivalente a una fórmula 2SAT, cuya satisfacción se puede determinar en tiempo polinómico.( x ∨ y ) ∧ ( ¬ x ∨ ¬ y )(x⊕y)(x∨y)∧(¬x∨¬y)

DW
fuente