## 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