MIN-2-XOR-SAT y MAX-2-XOR-SAT: ¿son NP-hard?

13

¿Cuál es la complejidad de MIN-2-XOR-SAT y MAX-2-XOR-SAT ? ¿Están en P? ¿Son NP-hard?

Para formalizar esto más precisamente, dejemos

Φ(x)=inCi,

donde x=(x1,,xm) y cada cláusula Ci tiene la forma (xixj) o (xi¬xj) .

El problema 2-XOR-SAT es encontrar una asignación a x que satisfaga Φ . Este problema está en P , ya que corresponde a un sistema de ecuaciones lineales mod 2 .

El problema de MAX-2-XOR-SAT es encontrar una asignación a x que maximice el número de cláusulas que se satisfacen. El problema MIN-2-XOR-SAT es encontrar una asignación a x que minimice el número de cláusulas que se satisfacen. ¿Cuáles son las complejidades de estos problemas?

¿Está inspirado en MIN o MAX-True-2-XOR-SAT NP-hard?

DW
fuente

Respuestas:

6

Perdón por responder una publicación anterior

(xixj)

G

Por ejemplo:

(x1x2)(x1x3)(x2x3)(x1x4)

Tenemos un gráfico como este:

grafo no bipartito

eso no es bipartito

Hay tres cláusulas que son satisfactorias, por lo que tenemos que eliminar una ventaja.

kk

Para hacer la reducción, simplemente creamos un nuevo literal para cada vértice y creamos una cláusula para cada borde que conecta dos literales

Por ejemplo:

Tenemos este gráfico,

grafo no bipartito 2

(x1x2)(x1x4)(x2x4)(x2x3)(x4x5)(x3x5)

kk

Rotia
fuente
1
Debe hacer explícita la implicación: dado que MAX-CUT es NP-Hard, la reducción a MAX-XORSAT significa que también es NP-Hard.
Antimonio
-1

(xixj)xixixjxixjxixj es cierto si los vértices correspondientes tienen asignados diferentes colores en el gráfico.

Si todos los vértices de la gráfica se pueden colorear con 2 colores y ninguno de los dos vértices con un borde compartido común tiene asignado el mismo color, entonces la ecuación es satisfactoria.

Pero un gráfico es de 2 colores si es un gráfico bipartito. Y determinar si un gráfico es bipartito se puede hacer en tiempo polinómico. Por lo tanto, el problema está en P, porque si podemos determinar en tiempo polinómico que el gráfico es un gráfico bipartito, entonces es solucionable, de lo contrario no es solucionable.

jcod0
fuente
1
(xixj)(xk¬xl)k,l(xk¬xl)
2
Esto me lleva a un problema más serio con su respuesta. El problema no es determinar si la fórmula es satisfactoria; El problema es identificar una asignación que satisfaga el número máximo / mínimo de cláusulas. Su algoritmo solo prueba si la fórmula es satisfactoria. Por lo tanto, resuelve 2-XOR-SAT, pero no resuelve MIN-2-XOR-SAT o MAX-2-XOR-SAT, pero ya sabía que 2-XOR-SAT está en P, como se explica en la pregunta. ¿He entendido mal algo?
DW
xixk
1
Pero todavía no veo cómo esto aborda mi segundo comentario. Has resuelto un caso especial de un problema que no estaba preguntando. En resumen, esta respuesta no responde la pregunta que hice.
DW