I have a large (~1k) number of boolean formulas like:

f1(x) = p1 AND p2
f2(x) = (p1 AND p2) OR p3
f3(x) = p4 OR !p5

The argument x is a set, and the predicates (the p's) assert that a certain condition is met on the set (typically, that x contains a certain value).

For every input, I have to evaluate all the formulas.

As an example, given a chair, f1 would say: the chair is red and the chair has a head rest, f2 would say f1 OR the chair was built before 1980 and so forth.

Some predicates invalidate the formulas statistically sooner than others in my data set; one of them would be, for example, the chair was built before 1900 (not many very old chairs are found).

If I scan all the formulas, find the pieces of them that are equal, like in this example, the first part of f1 and f2, is there a way to build a common parse tree that lets me use this information to make evaluating all the formulas faster?

  • 1
    $\begingroup$ You've just explained how to build a common "parse tree" given that you identify "shortcuts" (common subexpressions that only need to be evaluated once). The real question is how to find these shortcuts, possibly by massaging the formulas. In general it is believed to be intractable, though there might be good heuristics that work in your case. $\endgroup$ – Yuval Filmus Dec 14 '17 at 18:24
  • 2
    $\begingroup$ Several OBDD libraries have this capability: en.m.wikipedia.org/wiki/Binary_decision_diagram $\endgroup$ – jmite Dec 14 '17 at 18:33

This is the circuit minimization / logic optimization problem. You have a circuit with some number of inputs (one per predicate p1, .., pn; or based on the representation of x) and ~ 1k outputs (one per formula f1, .., fm). Now the goal is to construct another equivalent circuit that computes the same output, as efficiently as possible. That's a circuit minimization problem. The problem is hard in general, but there are some heuristics and tools that may be effective in many situations (e.g., Espresso, Quine-McClusky, BDDs, and more). I suggest reading about that subject and trying out one of those tools or techniques.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.