Conversion DNF en CNF: facile ou difficile

En ce qui concerne le thread Prouvant que la conversion de CNF en DNF est NP-Hard (et un thread Math connexe ):

Que diriez-vous de l'autre direction, de DNF à CNF? Est-ce facile ou difficile?

À la page 2 de cet article , ils semblent suggérer que les deux directions sont également difficiles quand elles disent " Nous nous intéressons à l'explosion maximale de la taille lors du passage de la représentation CNF à la représentation DNF (ou vice versa) ".

Mais DNF-SAT est en P et CNF-SAT est NP- complet. Donc, étant donné une expression DNF , il devrait y avoir une expression CNF non satisfaisante dont la longueur est polynomiale dans la longueur de . Et la conversion peut être effectuée en temps poly. Est-ce correct?$\phi_1$$\phi_2$$\phi_1$$\phi_1 \to \phi_2$

Edit: Modifié équivalent à equisatisfiable (c'est-à-dire que des variables supplémentaires sont autorisées dans ).$\phi_2$

Si vous souhaitez introduire des variables supplémentaires, vous pouvez convertir la forme DNF en CNF en temps polynomial en utilisant la transformée de Tseitin . La formule CNF résultante sera non satisfaisante avec la formule DNF d'origine: la formule CNF sera satisfiable si et seulement si la formule DNF d'origine était satisfaisable. Voir également https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Si vous ne voulez pas autoriser l'introduction de variables supplémentaires, la conversion de DNF en CNF est co-NP-difficile. En particulier, tester si une formule DNF est une tautologie est co-NP-difficile. Cependant, tester si une formule CNF est une tautologie peut être fait en temps polynomial (il suffit de vérifier séparément si chaque clause est une tautologie, ce qui est facile car chaque clause est une disjonction de littéraux). Par conséquent, si vous pouviez convertir la forme DNF en forme CNF en temps polynomial, sans introduire de nouvelles variables, alors vous obtiendriez un algorithme en temps polynomial pour tester si une formule DNF est une tautologie - quelque chose qui semble peu probable, étant donné que nous nous attendons P n'est pas égal à co-NP. Ou, pour le dire autrement, la conversion de DNF en CNF sans introduire de variables supplémentaires est co-NP-difficile.

Il s'agit de la différence entre équivalence et non- satisfaction . L'équivalence nécessite que les deux formules aient le même ensemble de solutions (et ne permettent donc pas d'introduire des variables supplémentaires). L'exquisatisfiabilité exige seulement que les deux formules soient satisfaisables ou les deux ne soient pas satisfaisantes (et permettent donc d'introduire des variables supplémentaires).