Strong Duality in Horn Minimization

摘要

A pure Horn CNF is minimal if no shorter pure Horn CNF representing the same function exists, where the CNF length may mean several different things, e.g. the number of clauses, or the total number of literals (sum of clause lengths), or the number of distinct bodies (source sets). The corresponding minimization problems (a different problem for each measure of the CNF size) appear not only in the Boolean context, but also as problems on directed hypergraphs or problems on closure systems. While minimizing the number of clauses or the total number of literals is computationally very hard, minimizing the number of distinct bodies is polynomial time solvable. There are several algorithms in the literature solving this task. In this paper we provide a structural result for this body minimization problem. We develop a lower bound for the number of bodies in any CNF representing the same Boolean function as the input CNF, and then prove a strong duality result showing that such a lower bound is always tight. This in turn gives a simple sufficient condition for body minimality of a pure Horn CNF, yielding a conceptually simpler minimization algorithm compared to the existing ones, which matches the time complexity of the fastest currently known algorithm.