### Abstract

We study the hardness of approximation of clause minimum and literal minimum representations of pure Horn functions in $n$ Boolean variables. We show that unless $\mathsf{P}=\mathsf{NP}$, it is not possible to approximate in polynomial time the minimum number of clauses and the minimum number of literals of pure Horn CNF representations to within a factor of $2^{\log^{1−o(1)}n}$. This is the case even when the inputs are restricted to pure Horn $3$-CNFs with $O(n^{1+\varepsilon})$ clauses, for some small positive constant $\varepsilon$. Furthermore, we show that even allowing sub-exponential time computation, it is still not possible to obtain constant factor approximations for such problems unless the Exponential Time Hypothesis turns out to be false.

Publication

*Annals of Mathematics and Artificial Intelligence* (2014) Vol. 71, Issue 4, pp 327-363