algorithm - 任意の命題式を CNF 形式に変換するための複雑さ

Question

命題式を CNF 形式に変換する際の複雑さはどれくらいですか? NP完全問題ですか？

Answer 1

最悪の場合、n節のWFFは2 ^ n節のCNFと同等であるため、一般的な論理式を同等のCNFに変換する標準アルゴリズムの実行時間は指数関数的です。

ただし、任意のブール式を多項式時間でCNFに変換できます。これは厳密には同等ではありませんが、ブール式が満足できる場合にのみ満足できます。これは、より一般的なSATがNP完全であることを前提として、3CNFがNP完全であることを証明するために使用される標準的な削減です。ここを参照してください。