DNF中的命题公式可以在多项式时间内决定吗？

Question

For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable: Just walk through all subformulas (l_1 and ... and l_k) and check, wheter it has NO complementary pair of literals.如果存在这种亚构象，则Formula F是可满足的。

我上面的方法正确吗？

如果是的，我想知道为什么所有现代的SAT求解器都将CNF作为输入格式，而不仅仅是使用DNF。

Answer 1

从CNF到DNF的转换可以以指数成本成本。例如，$（a_1 lor b_1） land cdots land（a_n lor b_n）$扩展到$ 2^n $很多条款。当您评论时，对于DNF的满意度很容易 - 这是很难的错误性。如果问题是微不足道的，则不会将其输入SAT求解器，这就是为什么SAT求解器接受CNF而不是DNF的原因。

如果您认为P与NP不同，那么这意味着没有多项式的时间将CNF满意度转换为DNF的满意度，因为前者是NP的完整时间，而后者则在P中。