La minimizzazione delle espressioni booleane NP-Complete?

Question

So che la soddisfazione booleana è NP-Complete, ma la minimizzazione / semplificazione di un'espressione booleana, con la quale intendo prendere una data espressione in forma simbolica e produrre un'espressione equivalente ma semplificata in forma simbolica, NP-Complete? Non sono sicuro che ci sia una riduzione dall'affidabilità alla minimizzazione, ma penso che probabilmente ci sia. Qualcuno lo sa per certo?

Answer 1

Bene, guardalo in questo modo: usando un algoritmo minimizzante, puoi compattare qualsiasi espressione non soddisfacente con il false letterale, giusto? Questo risolve efficacemente SAT. Quindi almeno un algoritmo minimizzante completo è destinato a essere NP-completo NP difficile.