Exclusivo 3SAT a Única 1-no-3SAT

Question

Suponha que eu tenha uma fórmula CNF, com cláusulas de tamanho 2 e 3.Tem um sistema único de satisfazer atribuição.

Ela foi feita a partir de um binário de multiplicação circuito onde eu multiplicado dois primos de números A e B tais que A*B=S, onde S é um semiprime número.Eu adicionei as condições que Um != 1, B != 1 e <= B e, em seguida, adicionado o valor de S para a fórmula certifique-se de que a atribuição é exclusiva.A única maneira de satisfazer a fórmula é colocar os valores de primos A e B na ordem correcta na entrada de bits.

1-no-3SAT, nós a força que exatamente 1 literal deve ser verdadeiro em cada trio e outros dois falsos.Se exatamente 2 literais são verdadeiras, podemos inverter todos os iterals na cláusula obter uma equivalente 1-no-3SAT cláusula (em outras palavras 2-em-3SAT é o mesmo problema).

Observação básica:Enquanto uma regulares OU cláusula elimina 1 possibilidade dos 8, 1 em 3 cláusula elimina 5 possibilidades de 8.

3SAT pode ser reduzida para 1-em-3 SAT, tal que se o 3SAT fórmula é satisfatível, então, então, é a diminuição da fórmula.

No entanto, as reduções não parecem preservar o número de atribuições, através da introdução de novas variáveis, sem forçar o seu valor.

Pode Único 3SAT ser reduzida a Única 1-no-3SAT...

1. Sem saber a atribuição correta?
2. Se não, sabendo a atribuição correta?

Answer 1

Sim, um 3-SAT fórmula $\phi$ pode ser transformado em um 1-em-3 SAT fórmula $\phi'$ preservando o número de satisfazer atribuições.Para evitar ambigüidades vou usar "$\vee$"entre literais de 3-SAT cláusula, e vírgulas entre literais de 1 em 3 SAT cláusula.

---

Deixe-me preliminares mostram que, dado dois literais $a$ e $b$, podemos simular um novo tipo de cláusula $(x = a \wedge b)$ que forças o valor de uma variável $x$ para ser $a \cunha b$ usando apenas 1 em 3 SAT restrições, sem a introdução de qualquer nova solução.

Considere o cluases:$$ (\overline{b}, c, x) \cunha (a, c, d) \cunha (\overline{a}, e, x) \cunha (b, e, f) $$

Se $a= op$, e $b= op$, e , em seguida, o 2º e 4º cláusulas garante que $c=d=e=f=\bot$.1ª e 3ª cláusulas garante, em seguida, que $x= op$.

Se $a= op$, e $b=\bot$, e , em seguida, a 2ª cláusula garante que $c=d=\bot$.1ª cláusula garante, em seguida, que $x=\bot$.A cláusula 3ª garante que $e= op$, e a 4ª cláusula implica $f=\bot$.

O caso $a=\bot$, e $b= op$ é simétrica.

Se $a=\bot$ e $b=\bot$, e , em seguida, o 1º e 3º cláusulas implica $c=e=x=\bot$.O 2º e 4º cláusulas garantir $d=f= op$.

---

Agora estou pronto para transformar uma fórmula $\phi$ de 3SAT uma fórmula $\phi'$ de 1 para 3 SENTOU-se.Considere-se agora uma cláusula $(a \vee b \vee c)$ de $\phi$.Esta pode ser transformada na seguinte equivalente 1-em-3 SAT cláusulas:

• Adicionar uma nova variável $x$ o que é verdadeiro iff $a$ é falsa e $b$ é verdade.Este é codificado pela cláusula $(x = \overline{a} \wedge b)$.

• Adicionar uma nova variável $y$ o que é verdadeiro iff $a$ é falso, $b$ é falso, e $c$ é verdade.Precisamos de uma variável adicional $z$.A cláusula $(z = \overline{a} \wedge \overline{b})$ assegura que $z$ é verdadeiro se, e somente se, $a$ é falsa e $b$ é falso.Em seguida, o valor de $y$ pode ser aplicada a cláusula $(y = z \cunha c)$.

• Se $(a \vee b \vee c)$ é verdade, pelo menos um dos $a$, $b$, ou $c$ é verdade.Isso significa que, exatamente um dos $a$, $x$, e $y$ é verdade.No inverso, se $(a \vee b \vee c)$ é falso e, em seguida, em todos os $a$, $x$, e $y$ são falsas.Isso mostra que $(a \vee b \vee c)$ é satisfatível se e somente se $(a, x, y$) é satisfatível.

Temos construído, em seguida, um equivalente de 1 em 3 SAT fórmula $\phi'$ que utiliza um conjunto de variáveis do original 3 SAT fórmula $\phi$.Uma verdade atribuição às variáveis de $\phi'$ satisfaz $\phi'$ se, e somente se, a atribuição restrita para as variáveis de $\phi$ satisfaz $\phi$.Portanto, se qualquer solução nova para $\phi'$ é introduzido, deve ser porque recentemente adicionados variáveis $x$, $y$, e $z$ (um conjunto para cada cláusula).No entanto, os valores dessas variáveis são completamente determinada pelos valores das variáveis de $\phi$.

Answer 2

Tal redução é descrito no Apêndice B do Régis Barbanchon, No único gráfico 3-coloração e parcimoniosa reduções no plano.Barbanchon atribui-lo a um trabalho anterior ([9] na bibliografia).Em outro lugar, eu tenho visto uma atribuição para Schaefer celebra-se o papel em que ele prova a sua famosa dicotomia teorema, entre outra coisa, dando-se uma redução de 3SAT 1-no-3SAT, que supostamente é parcimonioso (eu não verificado).