Menu
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?
988
Minimization refers to the process in which we simplify the algebraic expressions of any given boolean function. This process is very important as it helps in the reduction of the overall cost and complexity of an associated circuit.
Minimization can be done using Algebraic Manipulation or K-Map method.
There are a number of methods for simplifying Boolean expressions: algebraic, Karnaugh maps, and Quine-McCluskey being the more popular. We have already discussed algebraic simplification in an unstructured way. We now study Karnaugh maps (K-Maps).
The satisfiability problem (SAT) is to determine whether a given boolean expression is satisfiable. We can view SAT as the language { E | E is the encoding of a satisfiable boolean expression }. In 1971 using a slightly different definition of NP-completeness, Steven Cook showed that SAT is NP-complete.
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.
88
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
