Hardness Results for Approximate Pure Horn CNF Formulae Minimization

Endre Boros, Aritanan Gruber

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 po…