La minimizzazione delle espressioni booleane è NP-Complete?

Question

So che la soddisfacibilità booleana è NP-Complete, ma è la minimizzazione/semplificazione di un'espressione booleana, con cui intendo assumere un'espressione data in forma simbolica e produrre un'espressione equivalente ma semplificata in forma simbolica, NP-Complete? Non sono sicuro che ci sia una riduzione dalla soddisfacibilità alla minimizzazione, ma mi sembra che ci sia probabilmente. Qualcuno lo sa per certo?

Answer 1

Bene, guarda in questo modo: utilizzando un algoritmo di minimizzazione, puoi compattare qualsiasi espressione non soddisfacente per il letterale false, giusto? Questo risolve efficacemente SAT. Quindi almeno un algoritmo di minimizzazione completo è necessariamente NP-completo NP rigido.