Hardness results for approximate pure Horn CNF formulae minimization

Endre Boros, Aritanan Gruber

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 (Formula presented.). This is the case even when the inputs are restricted to pure Horn 3-CNFs with O(n1+ε) clauses, for some small positive constant ε. 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.

Original languageEnglish (US)
Pages (from-to)327-363
Number of pages37
JournalAnnals of Mathematics and Artificial Intelligence
Issue number4
StatePublished - Aug 1 2014

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Applied Mathematics


  • Artificial intelligence
  • Boolean functions
  • Computational complexity
  • Hardness of approximation
  • Propositional Horn logic


Dive into the research topics of 'Hardness results for approximate pure Horn CNF formulae minimization'. Together they form a unique fingerprint.

Cite this