ブール式の最小化はNP完全ですか？

Question

私はブールの充足可能性がNP完全であることを知っていますが、ブール式の最小化/簡略化です。これは記号式で与えられた式を取って、私は、充足可能性から最小化への削減があるとは確信していませんが、おそらくそこにいるように感じます。誰かが確かに知っていますか？

Answer 1

このように見てください：最小化アルゴリズムを使用すると、満足できない式をリテラルfalseに圧縮できますか？これは効果的にSATを解決します。したがって、少なくとも完全な最小化アルゴリズムは、 NP-完全NPハードに束縛される。