La minimizzazione delle espressioni booleane NP-Complete?
-
03-07-2019 - |
Domanda
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?
Soluzione
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.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow