We now show that building decision committees is a hard algorithmic task when one strives to obtain both small and accurate formulas. There are two usual notions of size which can naturally be used for decision committees. The first one is the whole number of literals of the formula (if a literal is present times, it is counted times) [Nock Gascuel1995,Nock Jappy1998], the second one is the number of rules of the formula [Kearns et al.1987]. Our results imply that regardless of the restriction over the values of the vectors (as long as they are elements of a set with cardinality ), and already for two-classes problems, minimizing the size of a decision committee for both size definitions is as hard as solving well-known -Hard problems. Therefore, the task is also hard for DC with the particular values , , for the vectors.

- The Size of a DC is Measured as its Whole Number of Literals
- The Size of a DC is Measured as its Number of Rules

©2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.