Fast algorithm to invert a boolean sum of products

Question

I'm trying to implement a very very fast boolean expression engine. I'm using it to represent states in very large state spaces, so I need it to handle as many operations per second as possible. At the very base of this engine is a sum of products. I am running up against an issue optimizing the NOT operator though. For example, if I have a sum of products with N minterms where each minterm has around M variables, then trying to invert that would create M^N minterms which would then be simplified using the espresso algorithm. I can speed it up a little and save some memory if I run the espresso algorithm intermittently during the inverse operation, but that's not enough. I doubt I am the first person to run into this problem, and I have tried doing the research, but I can't seem to find an efficient way to do this.

Can anybody point me in the right direction?

Answer 1

So, its been 5 years since I posted this question. After recently rediscovering it, I realized that I committed the cardinal sin. At some point between then and now I found a fairly fast algorithm to get this done and never came back to answer the question. The problem is that I've lost all associated documentation. Welp... here it is. I'll update this answer if I rediscover the source.

https://github.com/nbingham1/boolean/blob/a0f21eb1808dbcf86a3360ea85ab4eae15f5bf49/boolean/cover.cpp#L1055

EDIT: found the source

Multiple-Valued Logic Minimization For PLA Synthesis by Richard L. Rudell, page 58

https://apps.dtic.mil/dtic/tr/fulltext/u2/a606736.pdf

This uses Generalized Shannon Expansion, recursively complementing the two sides of the expansion and merging the complements with a simplifying heuristic.