¿Es minimización de expresiones booleanas NP-Completa?

Question

Sé que la satisfacibilidad booleana es NP-Completa, pero es la minimización / simplificación de una expresión booleana, con lo que me refiero a tomar una expresión dada en forma simbólica y producir una expresión equivalente pero simplificada en forma simbólica, ¿NP-Completa? No estoy seguro de que haya una reducción de la satisfacción a la minimización, pero creo que probablemente lo haya. ¿Alguien lo sabe con seguridad?

Answer 1

Bueno, véalo de esta manera: utilizando un algoritmo de minimización, puede compactar cualquier expresión no satisfactoria al literal false , ¿verdad? Esto resuelve efectivamente SAT. Por lo tanto, al menos un algoritmo de minimización completo debe estar NP-complete NP hard.