Complejidad de calcular la paridad de la fórmula CNF de lectura dos veces opuesta (

En una fórmula CNF de lectura dos veces opuesta, cada variable aparece dos veces, una vez positiva y otra negativa.

Estoy interesado en el problema , que consiste en calcular la paridad del número de asignaciones satisfactorias de una fórmula CNF de lectura dos veces opuesta. $\oplus\text{Rtw-Opp-CNF}$

No pude encontrar ninguna referencia sobre la complejidad de tal problema. Lo más cercano que pude encontrar es que la versión de conteo es -completa (consulte la sección 6.3 de este documento ). $\#\text{Rtw-Opp-CNF}$ $\#\text{P}$

Gracias de antemano por tu ayuda.

Actualización 10 de abril de 2016

En este documento , se muestra que el problema es completo, sin embargo, la fórmula producida por la reducción de no está en CNF, y tan pronto como intentas convertirlo nuevamente en CNF obtienes un Fórmula de lectura tres veces. $\oplus\text{Rtw-Opp-SAT}$ $\oplus\text{P}$ $3\text{SAT}$
La versión monótona se muestra como -completa en este documento . En dicho documento, se menciona rápidamente al final de la sección 4: Valiant dice que está degenerado. No me queda claro qué significa exactamente ser degenerado, ni qué implica en términos de dureza. $\oplus\text{Rtw-Mon-CNF}$ $\oplus\text{P}$ $\oplus\text{Rtw-Opp-CNF}$

Actualización 12 de abril de 2016

También sería muy interesante saber si alguien ha estudiado alguna vez la complejidad del problema . Dada una fórmula CNF de lectura dos veces opuesta, dicho problema requiere calcular la diferencia entre el número de asignaciones satisfactorias que tienen un número impar de variables establecidas en verdadero y el número de asignaciones satisfactorias que tienen un número par de variables establecidas en verdadero. No he encontrado ninguna literatura al respecto. $\Delta\text{Rtw-Opp-CNF}$

Actualización 29 de mayo de 2016

Como señaló Emil Jeřábek en su comentario, no es cierto que Valiant haya dicho que el problema es degenerado. Solo dijo que una versión más restringida de ese problema, , es degenerada. Mientras tanto, sigo sin saber qué significa exactamente degenerar, pero al menos ahora parece claro que es sinónimo de falta de poder expresivo. $\oplus\text{Rtw-Opp-CNF}$ $\oplus\text{Pl-Rtw-Opp-3CNF}$

cc.complexity-theory ds.algorithms counting-complexity Giorgio Camerani
fuente

⊕Rtw-Opp-CNF es tan difícil como ⊕Rtw-Mon-CNF. Puede compilar el gadget de negación: (i0 v x0 v x1) (x1 v x2) (i1 v x0 v x2). Si i0 = i1, entonces peso = 0 (en el módulo 2). De lo contrario, peso = 1.

No puedo encontrar la reducción de ⊕Rtw-Mon-CNF a ⊕Rtw-Opp-CNF, pero encontré un algoritmo polinómico para resolver ⊕Rtw-Opp-CNF. Entonces ⊕Rtw-Opp-CNF es más simple.

No puedo encontrar una mención de ⊕Rtw-Opp-CNF en el artículo de Valiant. Afirma que ⊕Pl-Rtw-Opp-3CNF está "degenerado", pero eso implica varias restricciones adicionales.

Emil Jeřábek

@ EmilJeřábek: Definitivamente tienes razón. Fui engañado por mi ignorancia del significado de "degenerar" , y apliqué el mismo tipo de razonamiento que normalmente se aplica en presencia de resultados completos: si cierto problema está completo para alguna clase, eliminar las restricciones de él obviamente conserva la integridad. Incluso si todavía no sé qué significa exactamente "degenerar" , al menos ahora me queda claro que ese término es de alguna manera sinónimo de debilidad (es decir, falta de poder expresivo), por lo tanto, el razonamiento antes mencionado no puede aplicarse. He corregido la pregunta en consecuencia.

Giorgio Camerani

@Maciej: ¿En serio? ¿Cómo funciona tu algoritmo polinomial?

Giorgio Camerani

Respuestas:

Resulta que cada fórmula de lectura doble opuesta tiene un número par de tareas satisfactorias. Aquí hay una buena prueba de ello, aunque probablemente se podría eliminar la terminología de la teoría de grafos.

Sea una fórmula CNF de lectura opuesta dos veces. Sin pérdida de generalidad, ninguna cláusula contiene tanto una variable como su negación. $\phi$

Considere el gráfico cuyo conjunto de vértices son las cláusulas de , y para cada variable , agregamos un borde (no dirigido) que incide en las dos cláusulas que contienen . Nuestra suposición de WLOG en dice que este gráfico no tiene bucles automáticos. Además, piense en etiquetar cada borde por la variable que lo define; De esta manera podemos distinguir entre aristas paralelas. $G$ $\phi$ $x$ $x$ $\phi$

Una orientación de es un gráfico dirigido cuyos bordes están formados mediante la asignación de una dirección a cada borde en . Llame a una orientación de admisible si cada vértice de tiene un borde saliente. Es fácil ver que satisfagan las asignaciones a están en correspondencia biyectiva con las orientaciones admisibles de . $G$ $G$ $G$ $G$ $\phi$ $G$

Ahora afirmo que el número de orientaciones admisibles de es par. El argumento es "por involución": construyo un mapa con las siguientes propiedades: $G$ $\Phi$

está totalmente definido (cada orientación admisible está asignada en algún lugar) $\Phi$
envía orientaciones admisibles a orientaciones admisibles $\Phi$
es una involución ( es la identidad) $\Phi$ $\Phi \circ \Phi$
no tiene puntos fijos $\Phi$

Una vez que estos se establecen, podemos observar que las órbitas de tienen un tamaño de 2 y una partición de las orientaciones admisibles de . De ello se deduce que el número de orientaciones admisibles es par. $\Phi$ $G$

Para definir , deje que sea una orientación admisible y considere dividir en sus componentes fuertemente conectados. luego envía a la orientación formada al invertir todos los bordes dentro de los componentes fuertemente conectados. Las propiedades se verifican directamente: $\Phi$ $\vec{G}$ $\vec{G}$ $\Phi$ $\vec{G}$

Cada gráfico dirigido se puede dividir en componentes fuertemente conectados.
Considere el "DAG de componentes fuertemente conectados" en ; llámalo el gráfico del cociente. Tenga en cuenta que tendrá la misma estructura de cociente, ya que no afecta los bordes entre los SCC, y los gráficos fuertemente conectados permanecen fuertemente conectados al invertir todos sus bordes. Además, si un SCC tiene más de un vértice, todos sus vértices constituyentes tienen un borde entrante. Si un SCC tiene un solo vértice y no es una fuente en el cociente, entonces todos sus vértices constituyentes tienen un borde entrante. Entonces para mostrar $\vec G$ $\Phi(\vec G)$ $\Phi$ $\Phi(\vec G)$ $G$
$\Phi(\vec G)$ $\vec G$
$\vec G$

Andrew Morgan
fuente

Buena observación! Una forma más simple de ver esto (como usted dice, "eliminar la terminología de la teoría de grafos") es observar que si una asignación a satisface F, entonces la asignación a '(x) = 1-a (x) también satisface F. Esto se puede mostrar fácilmente por inducción en el número de variables de F.

holf

Φ

$\Phi$

0 \to 1 \to 2 \to 0 \to 3 \to 1

$0\to1\to2\to0\to3\to1$

0 \to 1 \to 2 \to 0

$0\to1\to2\to0$

0 \to 3 \to 1 \to 0

$0\to3\to1\to0$

x

$x$

\neg x \lor y \lor \neg z

$\neg x\lor y\lor\neg z$

\neg y \lor z

$\neg y\lor z$

(1, 1, 1)

$(1,1,1)$

(0, 0, 0)

$(0,0,0)$

Φ

$\Phi$

M

$M$

x

$x$

y

$y$

x

$x$

x

$x$

y

$y$

M

$M$

@Emil: Ah sí, tienes razón. Si entiendo bien su sugerencia, está diciendo dividir la orientación en componentes fuertemente conectados e invertir los bordes dentro de los componentes. Creo que esto funciona. Actualizaré mi respuesta en consecuencia. ¡¡Muchas gracias!!

Andrew Morgan

No estoy seguro de si mi idea es comprensible, así que explicaré el ejemplo de Giorgio:

$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$

Primero necesito cambiar esto en el formulario DNF:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Esto debería dar la misma respuesta. Y no importa si calculo el número de soluciones del módulo 2 para esto:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

o para esto:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Así que elijo el segundo. Tengo implicantes:

$i_0$ $( x_1 \land x_2 \land x_3 )$

$i_1$ $( \lnot x_1 \land \lnot x_3 \land x_4 )$

$i_2$ $( \lnot x_4 \land x_5 )$

$i_3$ $( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Ahora estoy construyendo un sistema de ecuaciones:

${j_0}\oplus{j_1} = 1$

${j_0}\oplus{j_3} = 1$

${j_0}\oplus{j_1} = 1$

${j_2}\oplus{j_3} = 1$

${j_3} = 1$

$x_6$

Maciej
fuente

Si mi pensamiento está bien, entonces la respuesta es "no". Por supuesto, supongo que la variable ocurre una vez en positivo y otra en negación.

Maciej

x_{4}

$x_4$

j_{1} \oplus j_{2}

${j_1}\oplus{j_2}$

j_{3}

$j_3$

j_{2}

$j_2$

j_{1}

$j_1$

j_{0}

$j_0$

-1

$\oplus\text{Rtw-Opp-CNF}$ ${f(X)}\oplus{g(X)}$ $f(X) \wedge g(X)$ $f(X)$ $g(X)$

$i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

$i_j$ $x_0\wedge{x_1}\wedge{\neg{x_2}}$

$2^k$ $i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

$i_0\vee{i_1}\vee{i_2}\vee{...}\vee{i_{n-1}}$

$a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$

1) tiene todas las variables,

2) cada variable ocurre exactamente una (si la variable ocurre dos veces, entonces tenemos positivo y negativo en un implicante, por lo que esto dará como 0).

$x_0$ $i_0$ $x_0$ $i_1$

${j_0}\oplus{j_1} = 1$

${j_0}$ ${j_1}$ $i_0$ $i_1$ $i_0$ $j_0$ $j_0$ $2^l$

Maciej
fuente

\oplus Rtw-Opp-CNF

$\oplus\text{Rtw-Opp-CNF}$

@ AndrewMorgan Pero una fórmula con una cláusula única que contenga todas las variables exactamente una vez no sería una fórmula de lectura doble. La restricción es exactamente dos veces, no como máximo dos veces.

Giorgio Camerani

x_{6}

$x_6$

(x_{1} \lor x_{2} \lor x_{3}) \land (\neg x_{1} \lor \neg x_{3} \lor x_{4}) \land (\neg x_{4} \lor x_{5}) \land (\neg x_{2} \lor \neg x_{5} \lor \neg x_{6})

$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$

x_{6}

$x_6$

(x_{1} \lor x_{2}) \land (\bar{x_{1}}) \land (\bar{x_{2}})

$(x_1 \vee x_2) \wedge (\bar{x_1}) \wedge (\bar{x_2})$

(x_{1} \lor x_{2}) \land (\bar{x_{1}} \lor \bar{x_{2}})

$(x_1 \vee x_2) \wedge (\bar{x_1} \vee \bar{x_2})$

(x_{1}) \land (\bar{x_{1}}) \land (x_{2}) \land (\bar{x_{2}})

$(x_1) \wedge (\overline{x_1}) \wedge (x_2) \wedge (\overline{x_2})$

@ AndrewMorgan OK, ahora veo. Sin embargo, tenga en cuenta que también en la familia de casos a los que se refería, el número de tareas satisfactorias parece mantenerse incluso. La pregunta planteada por Maciej en su comentario resulta desafiante.

Giorgio Camerani