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.
heuristics.)(Just what are you trying to achieve to what end?) $\endgroup$