Prouver que la conversion de CNF en DNF est NP-Hard

20

Comment puis-je prouver que la conversion de CNF en DNF est NP-difficile?

Je ne demande pas de réponse, juste quelques suggestions sur la façon de le prouver.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
la source
5
Pour une analyse approfondie, jetez un œil à cet article "Sur la conversion de CNF en DNF"
Vor
@ A.Schulz: la définition originale dans l'article de Steve Cook le définit en utilisant des réductions Cook. Il semble que ce soit la réduction utilisée lors de la discussion sur la dureté NP générale en.wikipedia.org/wiki/NP-hard
Kaveh
La conversion CNF <-> DNF n'est pas une décision, il faut donc que ce soit une langue. sa plus une fonction avec entrée et sortie et il doit être converti en un problème de décision pour demander si son en NP etc. pense que le problème de non décision a été prouvé pour conduire à une explosion exponentielle de taille [par exemple dans Vors ref] donc un La version NP complète du problème de décision [s'il y en a un] est probablement une simplification importante. aussi comme la référence Vors montre que la complexité réelle de la conversion CNF <-> DNF est un problème de recherche actif ... notez qu'il y a une certaine similitude avec l'efficacité de l'algorithme de compression ...
vzn
2
@vzn La question demande si c'est NP- dur, pas NP- complet. Cela signifie que l'adhésion à NP n'est pas requise, il ne doit donc pas être un problème de décision.
David Richerby

Réponses:

18

Informellement:

Dans DNF, vous pouvez choisir n'importe quelle clause comme vraie, pour rendre la formule vraie. Cela signifie qu'un DNF qui équivaut à un certain CNF, est essentiellement une énumération de toutes les solutions à booléen assis sur le CNF. Remarque, il peut y avoir un nombre exponentiel de solutions. Étant donné que la résolution de booléens sat pour CNF pour une solution unique est NP-complète, la conversion en DNF signifie essentiellement la résolution de chaque solution. Il est donc au moins aussi dur que Boolean SAT, et est donc NP-difficile.

Realz Slaw
la source