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?
+3
A:
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.
Konrad Rudolph
2009-03-01 16:45:11
Written a little more neatly this could be the reduction he was look for.
Ben S
2009-03-01 16:47:26
You and the original poster probably mean NP-hard. As far as I could find out the problem is not known to be in NP.
starblue
2009-03-01 20:17:17
starblue: no, we mean NP complete. SAT is actually THE classical NP complete problem, i.e. it was the first problem proven to be NP complete, and all others are directly or indirectly reduced to it. This, by the way, is all explained in the Wikipedia article.
Konrad Rudolph
2009-03-02 10:09:39
Of course I know that SAT is the prototypical NP-complete problem. But the question was about boolean minimization, and that is not known to be in NP.
starblue
2009-03-02 11:21:38
starblue: ok, I misunderstood. Yes, you're of course right. However (without having a formal proof), I intuitively “know” that it is a) decidable and b) solvable in polynomial time, given nondeterministic execution, thus making it an NP problem.
Konrad Rudolph
2009-03-02 11:56:22