Publication at Faculty of Mathematics and Physics |
2012
Abstract
In this short note 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.
Moreover, in case that the answer is affirmative we present a polynomial time algorithm which outputs a shortest DNF representation of the given function. Therefore the defined class of functions is a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time.
Finally, we present a generalization of the above class which is still recognizable in polynomial time, and for which the Boolean minimization problem can be approximated within a constant factor.