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 -