TY - JOUR

T1 - Hardness results for approximate pure Horn CNF formulae minimization

AU - Boros, Endre

AU - Gruber, Aritanan

N1 - Funding Information:
The authors gratefully acknowledge the partial support by NSF grants IIS 0803444 and by CMMI 0856663. The second author also gratefully acknowledge the partial support by the joint CAPES (Brazil)/Fulbright (USA) fellowship process BEX-2387050/15061676.
Publisher Copyright:
© 2014, Springer International Publishing Switzerland.

PY - 2014/8/1

Y1 - 2014/8/1

N2 - 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.

AB - 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.

KW - Artificial intelligence

KW - Boolean functions

KW - Computational complexity

KW - Hardness of approximation

KW - Propositional Horn logic

UR - http://www.scopus.com/inward/record.url?scp=84908113590&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84908113590&partnerID=8YFLogxK

U2 - 10.1007/s10472-014-9415-9

DO - 10.1007/s10472-014-9415-9

M3 - Article

AN - SCOPUS:84908113590

SN - 1012-2443

VL - 71

SP - 327

EP - 363

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

IS - 4

ER -