94-07 On the Complexity of Horn Minimization

DIMACS TR: 94-07

On the Complexity of Horn Minimization

Authors: Endre Boros and Ondrej Cepek

ABSTRACT
Boolean functions given in disjunctive normal form representation are considered in this paper. For a given function such a representation is typically not unique and different representations may consist of different number of terms. The problem of minimizing a Boolean formula ammounts to finding its equivalent representation which has the minimum possible number of terms. This problem is a well-known hard problem, where the difficulty stems largely from the fact that the satisfiability problem for general Boolean formulae in disjunctive normal forms is a NP-complete problem. There are however, special classes of Boolean formulae for which satisfiability is known to be polynomial, like Horn formulae arising in artificial intelligence or in relational database applications. The complexity of the minimization problem of Horn formulae was not known so far.

In this paper we show that, given a Horn formula, finding a disjunctive normal form equivalent to it and having the minimum possible number of terms is NP-complete.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-07.ps

DIMACS Home Page