Complexidade do cálculo da paridade de leitura duas vezes oposta à fórmula CNF (

Em uma fórmula CNF de leitura duas vezes oposta, cada variável aparece duas vezes, uma vez positiva e uma vez negativa.

Estou interessado na problema, que consiste em calcular a paridade do número de satisfazer as atribuições de um oposto fórmula CNF leitura duas vezes. $\oplus\text{Rtw-Opp-CNF}$

Não consegui encontrar nenhuma referência sobre a complexidade desse problema. O mais próximo que pude encontrar é que a versão de contagem é -complete (consulte a seção 6.3 neste documento ). $\#\text{Rtw-Opp-CNF}$ $\#\text{P}$

Agradeço antecipadamente por sua ajuda.

Atualização 10 de abril de 2016

No presente trabalho , o problema é mostrado para ser -completo, no entanto, a fórmula produzida pela redução de não está na CNF, e assim que você tentar convertê-lo de volta para CNF você recebe um fórmula de leitura três vezes. $\oplus\text{Rtw-Opp-SAT}$ $\oplus\text{P}$ $3\text{SAT}$
A versão monótona é mostrada como -complete neste documento . Nesse artigo, é mencionado rapidamente no final da seção 4: Valiant diz que é degenerada. Não está claro para mim o que significa ser degenerado exatamente, nem o que isso implica em termos de dureza. $\oplus\text{Rtw-Mon-CNF}$ $\oplus\text{P}$ $\oplus\text{Rtw-Opp-CNF}$

Atualização 12 de abril de 2016

Também seria muito interessante saber se alguém já estudou a complexidade do problema . Dada uma fórmula CNF de leitura duas vezes oposta, esse problema pede para calcular a diferença entre o número de atribuições satisfatórias com um número ímpar de variáveis definidas como true e o número de atribuições satisfatórias com um número par de variáveis definidas como true. Eu não encontrei nenhuma literatura sobre isso. $\Delta\text{Rtw-Opp-CNF}$

Atualização 29 de maio de 2016

Como apontado por Emil Jeřábek em seu comentário, não é verdade que Valiant disse que o problema é degenerado. Ele disse apenas que uma versão mais restrita desse problema, , é degenerada. Enquanto isso, continuo sem saber exatamente o que significa degenerar, mas pelo menos agora parece claro que é sinônimo de falta de poder expressivo. $\oplus\text{Rtw-Opp-CNF}$ $\oplus\text{Pl-Rtw-Opp-3CNF}$

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

⊕Rtw-Opp-CNF é tão difícil quanto ⊕Rtw-Mon-CNF. Você pode criar o gadget de negação: (i0 x x x v x1) (x1 x x2) (i1 x x0 x x2). Se i0 = i1, peso = 0 (no módulo 2). Caso contrário, peso = 1.

Não consigo encontrar redução de tRtw-Mon-CNF para ⊕Rtw-Opp-CNF, mas encontrei um algoritmo polinomial para resolver ⊕Rtw-Opp-CNF. Então, tRtw-Opp-CNF é mais simples.

Não consigo encontrar uma menção ao RTW-OPP-CNF no artigo de Valiant. Ele afirma que ⊕Pl-Rtw-Opp-3CNF é "degenerado", mas isso envolve várias restrições adicionais.

Emil Jeřábek 3.0 20/16

@ EmilJeřábek: Você está definitivamente certo. Fui enganado por minha ignorância sobre o significado de "degenerado" e apliquei o mesmo tipo de raciocínio normalmente aplicado na presença de resultados de completude: se um determinado problema é completo para alguma classe, a remoção de restrições obviamente preserva a integralidade. Mesmo que eu ainda não saiba exatamente o que "degenerar" significa, é pelo menos claro para mim agora que esse termo é de alguma forma um sinônimo de fraqueza (ou seja, falta de poder expressivo), portanto o raciocínio mencionado não pode ser aplicado. Corrigi a pergunta de acordo.

Giorgio Camerani

@Maciej: Sério? Como o seu algoritmo polinomial funciona?

Giorgio Camerani

Respostas:

Acontece que toda fórmula de leitura oposta duas vezes tem um número par de tarefas satisfatórias. Aqui está uma boa prova disso, embora provavelmente se possa eliminar a terminologia teórica dos grafos.

Deixe ser uma fórmula CNF-oposta de leitura duas vezes. Sem perda de generalidade, nenhuma cláusula contém uma variável e sua negação. $\phi$

Considere o gráfico cujo conjunto de vértices são as cláusulas de e, para cada variável , adicionamos uma aresta (não direcionada) incidente nas duas cláusulas que contêm . Nossa suposição do WLOG em diz que este gráfico não possui auto-loops. Além disso, pense em rotular cada aresta pela variável que a define; Desta forma, podemos distinguir entre arestas paralelas. $G$ $\phi$ $x$ $x$ $\phi$

Uma orientação de é um grafo orientado cujos bordos são formadas através da atribuição de uma direcção de cada extremidade em . Chame uma orientação de admissível se todo vértice de tiver uma aresta de saída. É fácil ver que satisfazem atribuições para estão em correspondência bijective com orientações admissíveis de . $G$ $G$ $G$ $G$ $\phi$ $G$

Agora eu afirmo que o número de orientações admissíveis de é par. O argumento é "por involução": construo um mapa com as seguintes propriedades: $G$ $\Phi$

é totalmente definido (toda orientação admissível é mapeada em algum lugar) $\Phi$
envia orientações admissíveis para orientações admissíveis $\Phi$
é uma involução ( é a identidade) $\Phi$ $\Phi \circ \Phi$
não tem pontos fixos $\Phi$

Uma vez que estes são estabelecidos, podemos observar que as órbitas dos tem tamanho 2 e particionar as orientações admissíveis de . Daqui resulta que o número de orientações admissíveis é par. $\Phi$ $G$

Para definir , deixe ser uma orientação admissível e considere quebrar em seus componentes fortemente conectados. envia para a orientação formada invertendo todas as arestas nos componentes fortemente conectados. As propriedades são então verificadas diretamente: $\Phi$ $\vec{G}$ $\vec{G}$ $\Phi$ $\vec{G}$

Todo gráfico direcionado pode ser particionado em componentes fortemente conectados.
Considere o "DAG de componentes fortemente conectados" em ; chame de gráfico quociente. Observe que terá a mesma estrutura de quociente, pois não afeta as arestas entre SCCs, e os gráficos fortemente conectados permanecem fortemente conectados ao reverter todas as suas arestas. Além disso, se um SCC tiver mais de um vértice, todos os seus vértices constituintes terão uma aresta de entrada. Se um SCC tiver apenas um único vértice e não for uma fonte no quociente, todos os seus vértices constituintes terão uma aresta de entrada. Então, para mostrar $\vec G$ $\Phi(\vec G)$ $\Phi$ $\Phi(\vec G)$ é admissível, basta mostrar que os SCCs que são fontes no quociente têm vários vértices. Mas isso segue o fato de que todo vértice no componente tem uma aresta de entrada, que deve vir de outro vértice no componente, pois não possui auto-loops e o componente é uma fonte no quociente. $G$
Esta situação resulta do facto da estrutura de quociente coincide com a estrutura do quociente . $\Phi(\vec G)$ $\vec G$
Por admissibilidade, tem um ciclo e, portanto, alguns CEC com uma borda dentro dele. $\vec G$

Andrew Morgan
fonte

Boa observação! Uma maneira mais simples de ver isso (como você diz, "eliminar a terminologia teórica dos grafos") é observar que, se uma atribuição a satisfaz F, então a atribuição a '(x) = 1-a (x) também satisfaz F. Isso pode ser mostrado facilmente por indução no número de variáveis de F.

holf 26/10/16

Φ

$\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 sim, você está certo. Se entendi bem sua sugestão, você está dizendo que quebra a orientação em componentes fortemente conectados e inverte as arestas nos componentes. Eu acho que isso funciona. Vou atualizar minha resposta de acordo. Muito obrigado!!

Andrew Morgan

Não tenho certeza se minha ideia é compreensível, por isso vou explicar no exemplo 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 )$

Primeiro, preciso alterar isso no formulário 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 )$

Isso deve dar a mesma resposta. E não importa se eu calcular o número de soluções módulo 2 para isso:

$( 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 )$

ou para isso:

$( 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 )$

Então, eu estou escolhendo o segundo. Eu tenho 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 )$

Agora estou construindo um sistema de equações:

${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
fonte

Se meu pensamento estiver correto, a resposta é "não". Obviamente, presumo que a variável ocorre uma vez em positivo e outra em negação.

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) tem todas as variáveis,

2) toda variável ocorre exatamente uma (se a variável ocorrer duas vezes, teremos positivo e negativo em um implicante, de modo que esse valor será 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
fonte

\oplus Rtw-Opp-CNF

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

@AndrewMorgan Mas uma fórmula com uma cláusula única contendo todas as variáveis exatamente uma vez não seria uma fórmula de leitura duas vezes. A restrição é exatamente duas vezes, não no máximo duas vezes.

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, agora eu vejo. No entanto, considere que também na família de casos que você quis dizer, o número de tarefas satisfatórias parece permanecer regular. A pergunta feita por Maciej em seu comentário acaba sendo desafiadora.

Giorgio Camerani