Next: Overview of WIDC Up: Building Small Accurate Decision Previous: The Size of a

## The Size of a DC is Measured as its Number of Rules

We now state and prove the equivalent of Theorem 1 with this new size notion.

Theorem 3   When the size of a DC is measured as its number of rules, it is -Hard to find the smallest decision committee consistent with a set of examples . The result holds even when the concept labeling the examples is a monotone-DNF formula, that is, a disjunction of conjunction (DNF), each without negative literals.

Proof: See the Appendix.
A previous work [Kearns et al.1987] proves a similar theorem concerning the minimization of the size of a DNF. Theorem 3 can be shown to be more general, as the class of DC with two rules strictly contains that of DNF with two monomials.
The statement of Theorems 1, 2, 3 as optimization problems was chosen for pure convenience ; replacing them by their associated decision problems (decide whether there exist a consistent formula whose size is no more than some fixed threshold) would trivially make the problems not only -Hard, but also -Complete.

Next: Overview of WIDC Up: Building Small Accurate Decision Previous: The Size of a