Hardness Results for Approximate Pure Horn CNF Formulae Minimization

Details Hardness Results for Approximate Pure Horn CNF Formulae Minimization Hardness Results for Approximate Pure Horn CNF Formulae Minimization

2012-04-16

arxiv.org/abs/1204.3529v1

Computer Science

Computational Complexity

17 pages

Scientific paper

For a pure Horn Boolean function on $n$ variables, we show that unless P=NP, it is not possible to approximate in polynomial time (in $n$) the minimum numbers of clauses and literals to within factors of $2^{O(\log^{1-o(1)} n)}$ even when the inputs are restricted to 3-CNFs with $O(n^{1+\varepsilon})$ clauses, for some small $\varepsilon>0$. Furthermore, we show that unless the Exponential Time Hypothesis is false, it is not possible to obtain constant factor approximations for these problems even having sub-exponential time (in $n$) available.

Affiliated with

Also associated with

No associations

Rating

Hardness Results for Approximate Pure Horn CNF Formulae Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness Results for Approximate Pure Horn CNF Formulae Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness Results for Approximate Pure Horn CNF Formulae Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6930