O 1-em-3 SAT permanece NP-difícil, mesmo que todas as variáveis ​​ocorram positiva e negativamente?

9

O problema padrão 1-em-3 SAT (ou XSAT ou X3SAT) é:
Instância : uma fórmula CNF com todas as cláusulas contendo exatamente 3 literais.
Pergunta : existe uma atribuição satisfatória configurando exatamente 1 literal por cláusula?

O problema é NP-completo e permanece difícil, mesmo se nenhuma variável ocorrer negada. Gostaria de saber se esse problema se torna fácil ou permanece difícil se for necessário que cada variável ocorra pelo menos uma vez de forma positiva e pelo menos uma vez de forma negativa .

A redução habitual do 3SAT mostrando que 1-in-3 SAT é substitui rígidos uma cláusula por cláusulas ( ¬ x um b ) , ( y b c ) , ( ¬ z c d ) onde a , b , c , d(xyz)(¬xab)(ybc)(¬zcd)a,b,c,dsão novos para cada cláusula. Portanto, essa redução não ajuda a responder à minha pergunta. Eu tive problemas para criar um gadget que mostre a dureza dessa variante, pois se exatamente 1 literal em uma cláusula for verdadeiro, então 2 literais não simétricos serão falsos. Se for fácil, pensar em termos de partições do conjunto de cláusulas pode fazê-lo, mas não vejo como.

Dominik Peters
fonte
Pode ser reduzido para 2 sentados?
21139 Joshua Herman
4
Xi(XiX¯iW)(XiX¯iY)(XiX¯iZ)(WYZ¯)
(W¯YZ)(WY¯Z)XiX¯i
3
Posso encorajá-lo a escrever uma resposta completa para sua própria pergunta, talvez com base na idéia de Neal young? (. Aliás, eu não sei por que é "insatisfatório" A redução é uma redução.)
DW
4
Se esse caso especial é realmente o que você mais gosta, talvez faça sentido editar sua pergunta para refletir essa restrição extra?
DW

Respostas:

2

Em um comentário, o OP expressou interesse em uma redução que gerou instâncias com 3 variáveis ​​distintas por cláusula. Aqui está uma abordagem simples:

A redução é de 1-em-3 SAT com 3 variáveis ​​distintas por cláusula:

  • Antes de tudo, inclua todas as cláusulas na fórmula de entrada como cláusulas na fórmula de saída.
  • F1F2F3(¬F1,F2,F3)(F1,¬F2,F3)(F1,F2,¬F3)
  • xx(x,x,F1)(¬x,¬x,F1)

Vamos verificar se essa redução faz o que queremos. As seguintes propriedades são o que queremos:

  1. Cada cláusula sempre tem três variáveis ​​distintas.
  2. Cada variável ocorre em alguma cláusula positivamente e em alguma cláusula negativamente.
  3. A fórmula de entrada é equivalente à fórmula de saída.

F1F2F3

F1F2F3FiF1(x,x,F1)(¬x,¬x,F1)x=¬xxxxFi

Mikhail Rudoy
fonte