Building Small Accurate Decision Committees (and Alike) is Hard

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 $i$ times, it is counted $i$ 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 $\geq 2$), and already for two-classes problems, minimizing the size of a decision committee for both size definitions is as hard as solving well-known $NP$-Hard problems. Therefore, the task is also hard for DC $_{\{-1,0,+1\}}$ with the particular values $-1$, $0$, $+1$ for the vectors.