É a minimização de expressões booleanas NP-completo?

Question

Eu sei que boolean satisfiability é NP-Completo, mas é a minimização / simplificação de uma expressão booleana, refiro-me a tomar uma determinada expressão na forma simbólica e produzindo uma expressão equivalente, mas simplificado de forma simbólica, NP-completo? Eu não tenho certeza de que há uma redução de satisfiability a minimização, mas eu sinto que há provavelmente é. Alguém sabe com certeza?

Answer 1

Bem, olhar para ele dessa forma: usando um algoritmo de minimização, você pode compactar qualquer expressão não-satisfiable ao false literal, certo? Isto resolve eficazmente sab. Assim, pelo menos um algoritmo de minimização completa é obrigado a ser NP-completos NP duro.