Conversão de DNF para CNF: Fácil ou Difícil

Em relação ao segmento Provando que a conversão de CNF para DNF é NP-Hard (e um segmento Math relacionado ):

E a outra direção, de DNF a CNF? É fácil ou difícil?

Na página 2 deste artigo , eles parecem sugerir que ambas as direções são igualmente difíceis quando dizem " Estamos interessados na ampliação máxima de tamanho ao mudar da representação CNF para a representação DNF (ou vice-versa) ".

Mas DNF-SAT está em P e CNF-SAT é NP- completo. Portanto, dada uma expressão DNF , deve haver uma expressão CNF equisatisfatável cujo comprimento seja polinomial no comprimento de . E a conversão pode ser feita em tempo poli. Isso está correto? $\phi_1$ $\phi_2$ $\phi_1$ $\phi_1 \to \phi_2$

Editar: Alterado equivalente a equisatisfatório (ou seja, variáveis adicionais são permitidas em ). $\phi_2$

complexity-theory logic satisfiability normal-forms Martin Seymour
fonte

Você pode ir de qualquer fórmula para um CNF que seja satisfatório exatamente quando a fórmula original estiver no tempo polinomial. É por isso que CNF-SAT é NP-completo. Qualquer instância SAT (um problema NP-completo) pode ser reduzida para CNF-SAT em tempo polinomial. Eu acho que traduzi-lo exatamente, não apenas preservando a satisfação sempre às vezes produz uma explosão exponencial, mas não posso dizer isso com certeza.

Jake

Consulte en.wikipedia.org/wiki/Tseitin_transformation . Essencialmente, se você permitir a introdução de variáveis auxiliares, poderá fazer essa transformação no tempo poli (aumentando o tamanho da fórmula no máximo linearmente).

Jschnei 06/04

Você precisará decidir se deseja permitir que sua conversão introduza novas variáveis ou se a fórmula convertida deve se referir ao mesmo conjunto de variáveis (sem novas variáveis). Este é um ponto sutil que tem um efeito dramático na resposta. Então, sobre o que você quer perguntar?

@ Jake Você pode ir de qualquer fórmula a uma CNF equisatisfatória porque a CNF-SAT é NP-completa. Não é realmente "por que" o CNF-SAT é NP completo: a prova usual de que o CNF-SAT é NP completo não envolve a conversão de fórmulas arbitrárias em CNF; ao contrário, traduz máquinas de Turing em fórmulas CNF.

David Richerby

Para DW e outros - eu tinha a equisatisfatabilidade em mente. Nesse sentido, parece que a equisatisfatibilidade é apenas uma redução (neste caso, para outra fórmula booleana).

Martin Seymour

Respostas:

Se você estiver disposto a introduzir variáveis adicionais, poderá converter do formato DNF para CNF no tempo polinomial usando a transformação Tseitin . A fórmula CNF resultante será equisatisfatória com a fórmula DNF original: a fórmula CNF será satisfatória se e somente se a fórmula DNF original for satisfatória. Veja também https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Se você não deseja permitir a introdução de variáveis adicionais, a conversão do formato DNF para CNF é co-NP-hard. Em particular, testar se uma fórmula DNF é uma tautologia é co-NP-difícil. No entanto, testar se uma fórmula CNF é uma tautologia pode ser feito em tempo polinomial (basta verificar separadamente se cada cláusula é uma tautologia, o que é fácil, pois cada cláusula é uma disjunção de literais). Portanto, se você pudesse converter do formato DNF para CNF no tempo polinomial, sem introduzir novas variáveis, obteria um algoritmo de tempo polinomial para testar se uma fórmula DNF é uma tautologia - algo que parece improvável, dado que esperamos P não é igual a co-NP. Ou, dito de outra maneira, a conversão do formato DNF para CNF sem a introdução de variáveis adicionais é co-NP-hard.

Essa é a diferença entre equivalência vs equisatisfiabilidade . A equivalência requer que as duas fórmulas tenham o mesmo conjunto de soluções (e, portanto, não permite a introdução de variáveis adicionais). A equisatisfatibilidade exige apenas que ambas as fórmulas sejam satisfatórias ou insatisfatórias (e, portanto, permitem a introdução de variáveis adicionais).

DW
fonte

@ Mehrdad, não use comentários para fazer novas perguntas. Temos uma 'Fazer uma pergunta' no canto superior direito, se você tiver uma nova pergunta. Mas, apenas uma pequena dica ... você pode ler a pergunta no topo desta página antes de fazer uma nova pergunta ... ou, nesse caso, postar este comentário. Não posso deixar de notar que você fez uma pergunta em que a resposta encontra-se na mesma página da sua pergunta.

@ DW: Opa, eu realmente vi o outro post um pouco depois e esqueci de remover meu comentário aqui, desculpe. Removido agora.

user541686