Transforme um CNF em um 3-CNF equivalente definido nas mesmas variáveis

8

(Publiquei esta pergunta no CS há dez dias, sem resposta desde então - então publico aqui.)

Qualquer fórmula CNF pode ser transformada em tempo polinomial em uma fórmula 3-CNF usando novas variáveis. Nem sempre é possível se novas variáveis ​​não são permitidas (por exemplo, a fórmula de cláusula única: ).( x 1 ∨ x 2 ∨ x 3 ∨ x 4 )(x1∨x2∨x3∨x4)

Vamos definir o problema (SAT para 3-SAT): Dado , uma fórmula CNF. É possível transformar em um 3-CNF equivalente definido nas mesmas variáveis que ? - onde "equivalente" significa com o mesmo conjunto de modelos.F F FFFF

Qual é a complexidade desse problema?

cc.complexity-theory complexity-classes sat Xavier Labouze
fonte
Por equivalente, você quer dizer equi-satisfatório, presumo?
precisa
1
Pelo contrário, "com o mesmo conjunto de modelos".
Xavier Labouze
fyi tseitin transform é o nome da transformação de -SAT para 3-SAT usando vars extras. parece que sua pergunta é algo como perguntar sobre a existência de um algoritmo de compactação para o SAT. parece que você deseja as mesmas soluções, encurtando as cláusulas para 3 ou menos variáveis. do EE, isso está relacionado à enumeração de todos os mintermos e à descoberta de coberturas mínimas e à pergunta se existe alguma que atenda aos critérios (nesse caso, todas as cláusulas 3 ou menos vars). parece ter potencialmente alta complexidade. nn
vzn
Talvez seja co-NP-complete: escolha uma fórmula 3CNF , crie uma nova fórmula com 4 novas variáveis . possui uma fórmula equivalente a 3CNF nas mesmas variáveis ​​se e somente se não for satisfatório. φ = C 1 ∧ . . . ∧ C n φ ' = ( Y 1 ∨ y 2 ∨ y 3 ∨ y 4 ) ∧ C 1 ∧ . . . ∧ C N y 1 , . . . , Y 4 φ ' φφ=C1∧...∧Cnφ′=(y1∨y2∨y3∨y4)∧C1∧...∧Cny1,...,y4φ′φ
Marzio De Biasi
@MarzioDeBiasi. Agradável ! No entanto, não estou certo de que é suficiente para provar a completitude do co-NP (de alguma forma, eu espero um compexity maior, mas é apenas uma intuição ...)
Xavier Labouze

Respostas:

6

(A partir do comentário acima) O problema parece difícil de coNP; a redução simples é de 3CNF-UNSAT (que é coNP-completa): dada uma fórmula 3CNF φ = C 1 ∧ . . . ∧ C m , estendê-lo adicionando uma nova cláusula com 4 novas variáveis:φ=C1∧...∧Cm

φ ' = ( Y 1 ∨ y 2 ∨ y 3 ∨ y 4 ) ∧ C 1 ∧ . . . ∧ C m

φ′= ( y1∨ y2∨ y3∨ y4) ∧ C1∧...∧Cm

φ ' tem uma fórmula 3CNF equivalente definido nas mesmas variáveis se e apenas se a fórmula original φ é insatisfatível.φ′φ

( ⇐ ) a fórmula 3CNF ( y 1 ∨ y 2 ∨ y 3 ) ∧ ( y 1 ∨ y 2 ∨ y 4 ) ∧ C 1 ∧ . . . ∧ C m é equivalente a φ ′⇐( y1∨ y2∨ y3) ∧ ( y1∨ y2∨ y4)∧C1∧...∧Cmφ′

( ⇒ ) supor que φ ' tem uma fórmula equivalente 3CNF φ " e que é satisfeita. Escolha uma tarefa satisfatória de e simplifique ambos e substituindo as variáveis pela verdade correspondente valores . Nós obtemos que é satisfatório se e somente se é satisfatório (ambos contêm apenas variáveis ). Claramente⇒φ′φ′′φ X = ⟨ ˙ x 1 , . . . , ˙ x n ⟩ φ φ ' φ " x i ˙ x i φ ' X φ " X y i φ ' X = ( y 1 ∨ y 2 ∨ y 3 ∨ y 4 ) φ " X ( y 1 ∨ ¬ y 2φX=⟨x˙1,...,x˙n⟩φφ′φ′′xix˙iφ′Xφ′′Xyiφ′X=(y1∨y2∨y3∨y4). Toda cláusula de contém no máximo três variáveis, portanto podemos escolher uma delas, por exemplo e usá-la para criar uma tarefa satisfatória para : que não é uma tarefa satisfatória para , levando a uma contradição.φ′′X∨ y 3 ) φ ' ⟨ y 1 = f um l s e , y 2 = t r u e , y 3 = f um l s e , Y 4 = t r u e , ˙ x 1 , . . . , ˙ x n ⟩ & Phi; "(y1∨¬y2∨y3)φ′⟨y1=false,y2=true,y3=false,y4=true,x˙1,...,x˙n⟩φ′′

Marzio De Biasi
fonte
Tks pela resposta. Eu não entendo o : eu teria dito que se é insastificável, o mesmo é , que é equivalente à cláusula vazia (tamanho 0). Para ), apenas pensando se , então é equivalente a ...( ⇐ ) & Phi; & Phi; ' ( ⇒ & Phi; = ( x ∨ ¬ x ) ( y 1 ∨ y 2 ∨ y 3 ∨ y 4 ) ∧ ( x ∨ ¬ x ) ( y 1 ∨ y 2 ∨ x ) ∧ ( y 3 ∨ y 4 ∨ ¬ x )(⇐)φφ′(⇒φ=(x∨¬x)(y1∨y2∨y3∨y4)∧(x∨¬x)(y1∨y2∨x)∧(y3∨y4∨¬x)
Xavier Labouze
@XavierLabouze: sim, o seu parece melhor. Em ( , suponho que exista um equivalente 3CNF e, em seguida, derivo uma contradição ao assumir que o original é satisfatório. Você acha que está errado? ( ⇐ ) ⇒ ) φ ′ φ(⇐)⇒)φ′φ
Marzio De Biasi
Você está certo - eu estava errado ao afirmar tem o mesmo conjunto de modelos que . ( Y 1 ∨ y 2 ∨ y 3 ∨ y 4 ) ∧ ( x ∨ ¬ x ) ( y 1 ∨ y 2 ∨ x ) ∧ ( y 3 ∨ y 4 ∨ ¬ x )(y1∨y2∨y3∨y4)∧(x∨¬x)(y1∨y2∨x)∧(y3∨y4∨¬x)
Xavier Labouze
Você notou que é igual a ? Você pode explicar o seguinte: "Nós obtemos que é satisfatório se e somente se for satisfatório", do que você está adicionando "(ambos contêm apenas variáveis )", como você pode ter certeza de que eles serão contém apenas ? Também não entendo a conclusão, você provou que a adição da cláusula 4 variáveis ​​ao 3-cnf a partir das mesmas variáveis ​​é coNP-Complete? ( Y 1 ∨ y 2 ∨ y 3 ) ∧ ( y 1 ∨ y 2 ∨ y 4 ) ( y 1 ∨ y 2 ) ∧ ( y 3 ∨ y 4 ) φ ' X φ " X y i y i(y1∨y2∨y3)∧(y1∨y2∨y4)(y1∨y2)∧(y3∨y4)φ′Xφ′′Xyiyi
Ilya Gazman
1
φ 1 = ( y 1 ∨ y 2 ∨ y 3 ) ∧ ( y 1 ∨ y 2 ∨ y 4 ) φ 2 = ( y 1 ∨ y 2 ) ∧ ( y 3 ∨ y 4 ) φ 1 φ 2 ( y 1 ∨ y 2 ∨ y 3 ∨ y 4 )φ1=(y1∨y2∨y3)∧(y1∨y2∨y4) e são satisfatórios, mas não são equivalentes (o mesmo conjunto de modelos): y1 = F, y2 = F, y3 = T, y4 = T é um modelo válido para mas não para . Na questão, estamos falando de fórmulas equivalentes. A prova se baseia no fato de que não pode ter o mesmo conjunto de modelos de nenhuma fórmula 3CNF. φ2=(y1∨y2)∧(y3∨y4)φ1φ2(y1∨y2∨y3∨y4)
Marzio De Biasi