satispy icon indicating copy to clipboard operation
satispy copied to clipboard

Prevent blow-up with or operator

Open yberman opened this issue 6 years ago • 1 comments

The library does distribution directly when ORing two CNFs together. This results in exponential blowup in certain cases

from satispy import Variable as v
reduce(lambda x, y: x|y, [v("x" + str(i)) & v("y" + str(i)) for i in range(100)])

Would it be within the scope of this libraries purpose to not do any algebraic simplifications until a solution is requested at which point it does https://en.wikipedia.org/wiki/Tseytin_transformation to produce a CNF?

yberman avatar Jun 10 '18 15:06 yberman

That's a good idea, and already did some research on the topic, but haven't implemented anything yet. I hope I can invest some time soon.

netom avatar Jun 20 '18 08:06 netom