Provando que a conversão de CNF para DNF é NP-Hard

20

Como posso provar que a conversão de CNF para DNF é NP-Hard?

Não estou pedindo uma resposta, apenas algumas sugestões sobre como proceder para provar isso.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
fonte
5
Para uma análise profunda em dar uma olhada para este papel "na conversão de CNF para DNF"
Vor
@ A.Schulz: a definição original no artigo de Steve Cook define usando reduções de Cook. Parece que a redução é usado quando se discute geral NP-dureza en.wikipedia.org/wiki/NP-hard
Kaveh
A conversão CNF <-> DNF não é uma decisão, solicite que seja um idioma. é mais uma função com entrada e saída e deve ser convertida em um problema de decisão para perguntar se está em NP, etc. acho que o problema de não decisão provou levar a uma explosão exponencial de tamanho [por exemplo, em Vors ref], portanto, um NP versão completa do problema de decisão [se houver algum] é provavelmente uma simplificação significativa. também como VORs ref mostra a complexidade real do CNF <-> conversão DNF é um problema de pesquisa ativa ... note que existe alguma semelhança com eficiência algoritmo de compressão ...
vzn
2
@vzn A pergunta pergunta se é NP- difícil, não NP- completo. Isso significa que a associação ao NP não é necessária, portanto não precisa ser um problema de decisão.
David Richerby

Respostas:

18

Informalmente:

No DNF, você pode escolher qualquer cláusula para ser verdadeira, para tornar a fórmula verdadeira. Isso significa que um DNF que é equivalente a um determinado CNF é basicamente uma enumeração de todas as soluções para booleanas no CNF. Observe que pode haver um número exponencial de soluções. Como a solução booleana para CNF para uma única solução é NP-complete, a conversão para DNF significa essencialmente resolver todas as soluções. Portanto, é pelo menos tão difícil quanto o Boolean SAT e, portanto, é NP-difícil.

Realz Slaw
fonte