Hardness Results for Approximate Pure Horn CNF Formulae Minimization
This work addresses computational hardness for researchers in theoretical computer science and Boolean function optimization, providing strong negative results that are incremental in refining known complexity bounds.
The paper tackles the problem of approximating the minimum number of clauses and literals in pure Horn CNF representations, showing that unless P=NP, polynomial-time approximation is not possible within a factor of 2^(log^(1-o(1)) n), even for restricted inputs like pure Horn 3-CNFs with O(n^(1+ε)) clauses.
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.