Few months ago I started to code message filtering for email. The filters are basically set of boolean operators, for example OR(Has(a), NOT(OR(Has(b),Has(c))), AND(Has(e), Has(f)))..., that decide whether some next action should be done.
Those expressions are created by other people and over time the rules became quite complicated. So I decided to write tests: message generator that takes filter definition and outputs message(s) that trigger corresponding action.
My naive approach was to generate DNF and satisfy some arbitrary clause. This solution, however, has very bad performance. Some filters ended up having millions of clauses, so I had to wait couple of minutes to even generate one single message.
I know I should not expect to get polynomial time algorithm, because that would solve 3-SAT, which is NP-complete. But I still think it should be possible to speed things up. I don't need to generate the whole DNF after all - just one clause. Or there might be other approaches I'm not aware of. Maybe some approximate functions that generate messages with high probability. Any ideas?