9

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?

sgibbons
  • 3,620
  • 11
  • 36
  • 31

1 Answers1

13

Well, look at it this way: using a minimisation algorithm, you can compact any non-satisfiable expression to the literal false, right? This effectively solves SAT. So at least a complete minimisation algorithm must be NP-hard.

As per the comment by Para Black, the problem (which is also known as the minimum equivalent DNF problem) was actually shown to be non-NP and Σ2P-complete by Chris Umans in 1998.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • Written a little more neatly this could be the reduction he was look for. – Ben S Mar 01 '09 at 16:47
  • 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 Mar 01 '09 at 20: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 Mar 02 '09 at 10:09
  • 1
    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 Mar 02 '09 at 11:21
  • 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 Mar 02 '09 at 11:56
  • This reduces SAT to boolean minimization. Can we reduce boolean minimization to SAT though? It would be interesting to see the construct used, I am guessing it goes through a number of NP complete problems on the way. To turn this NP complete, we can make a decision problem as "is this boolean formula minimized?" – Gregory Morse Aug 08 '21 at 08:09
  • 1
    This problem is indeed NP-hard, but not NP-complete. It is $\Sigma_2^P$-complete, though (i.e. it is on the second level of the polynomial hierarchy). See [this presentation](http://users.cms.caltech.edu/~dave/presentations/080107.pdf) or [this paper](https://ieeexplore.ieee.org/document/743506) for a proof. – Para Black Mar 28 '23 at 08:45
  • @ParaBlack That’s neat! Whenever somebody asks for an example of an NP-hard problem which isn’t in NP, the invariable answer is “halting problem”. Nice to find another concise example. – Konrad Rudolph Mar 28 '23 at 09:09