Boolean functions with long prime implicants
We introduce a class of Boolean functions defined by a minimum length of its prime implicants. We show that given a DNF one can test in polynomial time whether it represents a function from this class. We describe a polynomial time algorithm for finding a shortest DNF representation of the functions belonging to this class. We also present a generalization of the above class for which we can approximate the Boolean minimization problem within a constant factor.
dnf boolean minimization analysis of algorithms approximation algorithms consensus method set cover