Monotone 3-SAT com exatamente 3 variáveis distintas, intratáveis?

Question

Eu dei a seguinte variação do SAT:

.

Dada uma fórmula F no CNF onde cada cláusula C tem exatamente 3 literais distintos e para cada C em f ou todos os literais são positivos ou todos os literais são negados. Exemplo:

.

$ f= (x_1 \ vee x_2 \ vee x_4) \ wedge (\ NEG X_2 \ Vee \ NEG X_3 \ Vee \ Neg X_4) \ Wedge (x_3 \ Vee x_4 \ vee x_5) $

.

esta variação de SAT tractable?

Meus resultados até agora:

Eu suspeito que o problema é NP-completo e, portanto, não é tratável. Assim, gostaria de realizar uma poli-redução de 3-SAT para a variação descrita acima.

Uma fórmula arbitrária de 3 sat pode ser convertida em monótono 3-sat.

Assuma o exemplo seguinte:

$ c_1= (x_1 \ vee x_2 \ vee \ neg x_3) $ e definir $ z_3 $ por $ \ neg x_3 \ leftrightarrow z_3 $ e $ x_3 \ leftrightarrow \ neg z_3 $ que é equivalente para $ (x_3 \ vee z_3) \ Wedge (\ NEG X_3 \ Vee \ NEG Z_3) $ .

De que obtemos a forma monótona de $ c_1 $ por

$ (x_1 \ vee x_2 \ vee \ neg x_3) \ leftrightarrow (x_1 \ vee x_2 \ vee z_3) \ wedge (x_3 \ vee z_3) \ wedge (\ NEG X_3 \ Vee \ NEG Z_3) $

aplicando esta transformação a todas as cláusulas, recebo uma fórmula de 3 sat do monótono que é igualmente satisfável.

Minha redução produz 2 cláusulas adicionais com 2 literais para cada cláusula não monótona, mas como obtenho apenas cláusulas monótonas com exatamente 3 literais distintos?

Answer 1

Vou tentar responder agora minha própria pergunta e ficaria feliz com alguns alimentares sobre o coretness.

Como na questão acima discutida e apontada por Kyle Jones, podemos reduzir as fórmulas 3-SAT arbitrárias para as fórmulas Monotone 3-Sat.

Por exemplo, uma cláusula $ c= (x_1 \ ve x_2 \ vee \ neg x_3) $ pode ser convertido para $ C '(x_1 \ vee x_2 \ vee z_3) \ wedge (z_3 \ vee x_3) \ wedge (\ neg z_3 \ ve \ neg x_3) $ . Pode-se verificar se $ c $ é satisfatório $ c '$ também é satisfatório e se $ C $ não é satisfatório $ c '$ também não é satisfatório.

O próximo passo é converter todas as cláusulas com menos de 3 literais para cláusulas com exatamente 3 literais distintos.

Portanto, tome por exemplo $ c_1= (x_1 \ vee x_2) $ e transformá-lo para $ c_1 '= ( x_1 \ vee x_2 \ vee y_1) \ wedge (x_1 \ vee x_2 \ vee y_2) \ wedge (x_1 \ vee x_2 \ vee y_3) \ wedge (\ neg y_1 \ vee \ neg y_2 \ ve \ neg y_3) $ Então, novamente se $ c_1 $ é satisfatório $ c_1 '$ também é satisfatório e se $ c_1 $ não é satisfatório $ c_1 '$ também não é satisfatório. O mesmo pode ser feito para o caso negativo, ou seja, $ c_2= (\ neg x_1 \ ve \ neg x_2) $ pode ser transformado para $ C_2 '= (\ NEG X_1 \ Vee \ NEG X_2 \ Vee \ Neg u_1) \ Wedge (\ Neg X_1 \ Vee \ Neg X_2 \ Vee \ NEG U_2) \ Wedge (\ Neg X_1 \ Vee \ NEG X_2 \ vee \ neg u_3) \ cunha (u_1 \ vee u_2 \ vee u_3) $

aplicando as duas transformações, pode-se converter uma instância arbitrária de 3 sats para uma instância de Monotone 3-SAT com exatamente 3 literais distintos. Como pode ser visto facilmente acima das transformações têm complexidade polinômica. Portanto, desde 3-SAT é NP-Hard a redução ASWELL deve ser NP-HARD.