On approximate Horn minimization
It is known that minimizing Horn formulas is NP-hard, but
the problem has an efficient O(n)-approximation algorithm,
where n is the number of variables. We consider lower and
upper bounds for the approximability of different versions.
Joint work with Amitava Bhattacharya, Bhaskar DasGupta and