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

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 , , onde $(x\lor y \lor z)$ $(\lnot x \lor a \lor b)$ $(y\lor b\lor c)$ $(\lnot z \lor c \lor d)$ $a,b,c,d$ sã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.

cc.complexity-theory np-hardness sat Dominik Peters
fonte

Pode ser reduzido para 2 sentados?

21139 Joshua Herman

X_{i}

$X_i$

(X_{i} \lor {\bar{X}}_{i} \lor W) \land (X_{i} \lor {\bar{X}}_{i} \lor Y) \land (X_{i} \lor {\bar{X}}_{i} \lor Z)

$(X_i\vee \overline X_i \vee W) \wedge (X_i\vee \overline X_i \vee Y)\wedge (X_i\vee \overline X_i \vee Z)$

(W \lor Y \lor \bar{Z})

$(W \vee Y \vee \overline Z)$

(\bar{W} \lor Y \lor Z) \land (W \lor \bar{Y} \lor Z)

$(\overline W \lor Y\lor Z)\land(W\lor\overline Y \lor Z)$

X_{i} \lor {\bar{X}}_{i}

$X_i\lor\overline X_i$

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.)

Se esse caso especial é realmente o que você mais gosta, talvez faça sentido editar sua pergunta para refletir essa restrição extra?

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.
$F_1$ $F_2$ $F_3$ $(\neg F_1, F_2, F_3)$ $(F_1, \neg F_2, F_3)$ $(F_1, F_2, \neg F_3)$
$x$ $x'$ $(x, x', F_1)$ $(\neg x, \neg x', F_1)$

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

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

$F_1$ $F_2$ $F_3$

$F_1$ $F_2$ $F_3$ $F_i$ $F_1$ $(x, x', F_1)$ $(\neg x, \neg x', F_1)$ $x' = \neg x$ $x'$ $x'$ $x$ $F_i$

Mikhail Rudoy
fonte

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

Respostas:

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