0
$\begingroup$

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I have applied the Espresso Hueristic Logic Minimizer as implemented through the PyEDA library. Now, I would like to express this formula in such a way that the expression length is minimal.

The way I had thought to do this is to divide the expression into subexpressions and convert these subexpressions into either conjunctive or disjunctive normal form based on some heuristic (e.g. a greedy algorithm which selects the minimum length subexpression at each check). However, it appears to me that checking each subexpression will lead to exponential time complexity.

Are there any ideas as to how I might approach this? I believe that the problem is suited to the application of reinforcement learning.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ How large of an expression are we talking about? How many different variables does the formula have? $\endgroup$
    – Сергей Макеев
    Aug 20 '20 at 16:49
  • 1
    $\begingroup$ The problem is probably NP-hard (or worse) so I suspect any algorithm will be exponential time in the worst case. Are you aware of that? $\endgroup$
    – D.W. ♦
    Aug 21 '20 at 1:12
  • $\begingroup$ (An exact solution probably isn't practical, but then, you "start" from an intermediate result arrived at using heuristics.)(Just what are you trying to achieve to what end?) $\endgroup$
    – greybeard
    Aug 21 '20 at 4:21

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.