La minimisation des expressions booléennes est-elle NP-Complete?

Question

Je sais que la satisfiabilité booléenne est NP-Complete, mais est-ce que la minimisation / simplification d'une expression booléenne, ce qui signifie que je prends une expression donnée sous forme symbolique et produisant une expression équivalente mais simplifiée sous forme symbolique, NP-Complete? Je ne suis pas sûr qu'il y ait une réduction de la satisfiable à la minimisation, mais je pense que c'est probablement le cas. Est-ce que quelqu'un sait à coup sûr?

Answer 1

Eh bien, regardez-le de cette façon: en utilisant un algorithme de minimisation, vous pouvez compresser n'importe quelle expression non satisfiable en un faux littéral, n'est-ce pas? Cela résout efficacement SAT. Donc, au moins un algorithme de minimisation complet doit nécessairement être NP-complete NP hard.