formule propositionnelle DNF peut être décidé en temps polynomial?

Question

, on peut décider en temps polynomial Pour une formule propositionnelle donnée f dans DNF, si la formule est satisfaisable: Il suffit de marcher à travers tous les sous-formules (L_1 et ... et l_k) et le contrôle, il a wheter paire complémentaire de NO littéraux. Formule f est satisfaisable ssi tel existe sous-formule.

Mon approche ci-dessus correcte?

Si oui, je me demande pourquoi tous les solveurs SAT modernes obtenir un CNF comme format d'entrée, et ne pas seulement utiliser DNF.

Answer 1

La conversion de CNF à DNF peut venir à un coût exponentiel. Par exemple $ (A_1 \ lor B_1) \ terre \ terre \ cdots (a_n \ lor b_n) $ 2 $ se développe pour ^ n $ de nombreux termes. Comme vous le commentaire, pour DNF satisfiability est facile - il est falsifiabilité qui est difficile. Si le problème est trivial, vous ne saisissez pas à un solveur, et c'est pourquoi solveurs SAT acceptent CNF au lieu de DNF.

Si vous pensez que P est différent de NP, cela implique qu'il n'y a aucun moyen polynomiale pour convertir CNF satisfiability à DNF satisfiability, puisque le premier est NP-complet alors que ce dernier est en P.