formule propositionnelle DNF peut être décidé en temps polynomial?
-
16-10-2019 - |
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.
La solution
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.