Boolean functions with a simple certificate for CNF complexity (Q412324): Difference between revisions

Last section (Conclusion) of the paper: ``In this paper we have studied a lower bound on the minimum CNF size of a given function \(f\) represented by a CNF \(\varphi\). The lower bound which we have considered is given by ess\((f)\), which denotes the number of pairwise disjoint essential sets of implicates of \(f\). We are mainly interested in functions for which this lower bound matches the minimum CNF size. We have called such functions coverable, and we have shown in Sections 3 and 4 that if a class of Boolean functions \(\mathcal C\) is tractable and coverable, then the problem of minimization of functions in this class belongs to both NP and co-NP. This fact proves that such a minimization problem is not NP-hard (unless NP = co-NP), and thus indicates that it might in fact belong to P. In Section 5 we study the intersections of essential sets with the set of prime implicates, call these intersections prime essential sets and prove that many properties of essential sets carry over to prime essential sets. This fact allows us to restrict our attention to prime implicates only. We have also proved several negative results about ess\((f)\). In Section 6 we have shown that not every function is coverable and moreover, for every constant \(k\) we can construct a function \(f\) for which cnf\((f)\)/ess\((f)\geq k\). In Section 7 we have shown that the problem of checking whether ess\((f)\geq k\) is NP-complete if its input is pure Horn 3CNF. In Section 8 we have shown that this problem remains NP-complete even in the case when the input is allowed to be much larger, namely when the input function is represented by a truth table. On th other hand we have shown that a relaxed value of ess\((f)\) can be computed using linear programming. Given the fact that minimization seems to be easier for coverable functions than in the general case, one might ask whether it would be possible to check in polynomial time if a given function \(f\) is coverable, i.e., whether ess\((f) =\) cnf\((f)\). Unfortunately, it turns out that this problem is NP-complete even if the input is a pure Horn 3CNF. This result is not contained in the present paper because we have found the corresponding reduction just recently. On the other hand, all classes for which a polynomial time minimization algorithm is known to us are coverable. This gives an indication that if a tractable class of Boolean functions is found to be coverable, then we can hope for a polynomial minimization algorithm for it. From a theoretical point of view, it would therefore be interesting to find a class of Boolean functions which would be tractable and coverable, and yet we would not be able to find a polynomial minimization algorithm for it.''