I want to minimize DNF formula which has ~200k products combined into a sum. The depth of that formula is 2 - first level is the OR, and second level is AND for all conjunctions.

I have tried using the Espresso program to minimize it, but it only reduces the number of products from 200k to 50k. Espresso still retains the formula's depth of two, and there isn't an option to go deeper, it only puts "don't care" bits.

Are there any algorithms or techniques for taking a large DNF, and producing a smaller, more managable formula – one that isn't just product of sums, or sum of products?

If there isn't, how should one go about doing such task?

  • 1
    $\begingroup$ Requests for tools and programs are off-topic, here, so I've edited your question to be about algorithms and techniques. $\endgroup$ – David Richerby Nov 4 '18 at 13:50
  • $\begingroup$ isn't this 2-DNF? then the Espresso represented each product with a bit vector with equality operator and then put into a set. This may be the first step $\endgroup$ – kelalaka Nov 4 '18 at 21:02
  • $\begingroup$ Please define what you mean by "minimize" the formula. What are the requirements on the output? Can it be any circuit? Does it have to be in DNF? Does it have to be a formula? How do you measure its size? Most likely the problem is NP-hard (actually a bit harder). $\endgroup$ – D.W. Nov 5 '18 at 4:04
  • $\begingroup$ @D.W. by "minimize" the number of And/Or/(possibly xor, eq, not) operations would be minimal. It doesn't need to be in DNF since a formula of depth more than 2 would be a good start. It has to be a formula. I would be fine with an NP-hard solution, since any solution would be a good start at this point. $\endgroup$ – Nikola Dim Nov 5 '18 at 19:18
  • $\begingroup$ OK. Can you edit the question so that information is contained in the question, so people don't have to read the comments to understand what you are asking? Thank you. $\endgroup$ – D.W. Nov 5 '18 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.