  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 P=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.

Computational Complexity;Artificial Intelligence