Is minimization of boolean expressions NP-Complete?
-
03-07-2019 - |
Question
I know that boolean satisfiability is NP-Complete, but is the minimization/simplification of a boolean expression, by which I mean taking a given expression in symbolic form and producing an equivalent but simplified expression in symbolic form, NP-Complete? I'm not sure that there's a reduction from satisfiability to minimization, but I feel like there probably is. Does anyone know for sure?
Solution
Well, look at it this way: using a minimizing algorithm, you can compact any non-satisfiable expression to the literal false
, right? This effectively solves SAT. So at least a complete minimizing algorithm is bound to be NP-complete NP hard.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow