formula proposizionale in DNF può essere deciso in tempo polinomiale?

Question

Per una data formula f proposizionale in DNF, si può decidere in tempo polinomiale, se la formula è soddisfacibile: Solo a piedi attraverso tutti sottoformule (l_1 e ... e l_k) e di controllo, anche depurato che ha due NO complementare di letterali. Formula f è soddisfacibile se e solo se esiste tale sottoformula.

Il mio approccio di cui sopra corretto?

Se sì, mi chiedo il motivo per cui tutti i moderni risolutori SAT ottenere un CNF come formato di input, e non basta usare DNF.

Answer 1

La conversione da CNF a DNF può venire a un costo esponenziale. Ad esempio $ (a_1 \ lor q_1) \ terra \ cdots \ terrestri (a_n \ lor b_n) $ espande a $ 2 ^ n $ molti termini. Come si commenta, per DNF soddisfacibilità è facile - è falsificabilità che è difficile. Se il problema è banale, non lo fai in ingresso a un SAT solver, ed è per questo SAT risolutori accettano CNFs invece di DNFs.

Se credi che P è diverso da NP, allora questo implica che non v'è alcun modo un tempo polinomiale per convertire CNF soddisfacibilità di DNF soddisfacibilità, dal momento che il primo è NP-completo mentre il secondo è in P.