Hardness Results for Approximate Pure Horn CNF Formulae Minimization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
One head is better than two: a polynomial restriction for propositional definite Horn forgetting
Logical forgetting is \np-complete even in the simple case of propositional Horn formulae, and may exponentially increase their size. A way to forget is to replace each variable to forget with the body of each clause who…
Forgetting in short and heterogeneous sequences of belief revisions
Forgetting a specific belief revision episode may not erase information because the other revisions may provide or entail the same information. Whether it does was proved coNP-hard for sequences of two arbitrary lexicogr…
HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baseline
Industrial SAT formula generation is a critical yet challenging task. Existing SAT generation approaches can hardly simultaneously capture the global structural properties and maintain plausible computational hardness. W…
Superredundancy: A tool for Boolean formula minimization complexity analysis
A superredundant clause is a clause that is redundant in the resolution closure of a formula. The converse concept of superirredundancy ensures membership of the clause in all minimal CNF formulae that are equivalent to …
Belief merging within fragments of propositional logic
Recently, belief change within the framework of fragments of propositional logic has gained increasing attention. Previous works focused on belief contraction and belief revision on the Horn fragment. However, the proble…