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

Question

ブール充足可能性はNP完全であることを知っていますが、ブール式の最小化/単純化は、シンボリック形式の特定の式を取り、シンボリック形式の同等であるが単純化された式NP-Completeを生成することを意味しますか？充足可能性から最小化への低下があるかどうかはわかりませんが、おそらくそうだと思います。誰でも確かに知っていますか？

Answer 1

まあ、このように見てください：最小化アルゴリズムを使用して、満たされない式をリテラル false に圧縮できますよね？これにより、SATが効果的に解決されます。したがって、少なくとも完全な最小化アルゴリズムは NP-complete NP hardにバインドされます。