algorithm - ブール式の最小化はNP完全ですか?

Question

ブール値の充足可能性がNP完全であることは知っていますが、ブール式の最小化/単純化です。これは、特定の式を記号形式で取得し、同等であるが単純化された式を記号形式で生成することを意味します.NP完全ですか？充足可能性から最小化への減少があるかどうかはわかりませんが、おそらくあると思います。誰かが確かに知っていますか？

Answer 1

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