Die Aussageformel in DNF kann in Polynomzeit entschieden werden?

Question

Für eine bestimmte Aussageformel F in DNF kann man sich in Polynomzeit entscheiden, wenn die Formel befriedigend ist: Gehen Sie einfach alle Subformulas (L_1 und ... und L_K) und überprüfen Sie, ob es kein komplementäres Paar von Literalen gibt. Die Formel F ist befriedigend, wenn solche Subformeln existiert.

Ist mein Ansatz oben richtig?

Wenn ja, frage ich mich, warum alle modernen SAT -Solvers ein CNF als Eingabebildformat erhalten und nicht nur DNF verwenden.

Answer 1

Die Konvertierung von CNF in DNF kann exponentielle Kosten erfolgen. Zum Beispiel $ (a_1 lor b_1) land cdots land (a_n lor b_n) $ erweitert auf $ 2^n $ viele Begriffe. Wie Sie kommentieren, ist die Befriedigung für DNF einfach - es ist schwierig, fälschungsvoll zu fällen. Wenn das Problem trivial ist, geben Sie es nicht in einen SAT -Solver ein, und deshalb akzeptieren SAT -Solvers CNFs anstelle von DNFs.

Wenn Sie der Meinung sind, dass P von NP unterscheidet, bedeutet dies, dass es keine Polynomzeit gibt, um die CNF-Zufriedenheit in die Befriedigung der DNF umzuwandeln, da erstere NP-Complete ist, während sich letzteres in P. befindet.