DNFの命題式は、多項式時間で決定できますか？

Question

DNFの特定の命題式Fの場合、式が満たす可能性がある場合、多項式時間で決定できます。すべてのサブホルム（L_1および...およびL_K）を歩いて、補完的なリテラルペアがないことを確認します。式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ソルバーはDNFSの代わりにCNFSを受け入れます。

PがNPとは異なると思われる場合、これは、前者はP.後者がPにあるため、CNFの満足度をDNFの満足度に変換する多項式時間がないことを意味します。