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

Theorem 1   When the size of a DC is measured as its whole number of literals, it is $NP$-Hard to find the smallest decision committee consistent with a set of examples $LS$.

Proof: See the Appendix. $\hbox{\vrule width 0.8pt \vbox to6pt{\hrule depth 0.8pt width 5.2pt \vfill\hrule depth 0.8pt}\vrule width 0.8pt}$
We can easily adapt Theorem 1 to the case where the rules are replaced by weighted DT as advocated in boosted C4.5 [Schapire Singer1998]. Here, each tree returns a class $\in \{+1,-1\}$, and each tree is given a real weight to leverage its vote. The sign of the linear combination gives the class of an example. The following theorem holds again with any limitations on the leveraging coefficients (as long as at least one non-zero value is authorized), or without limitation on the coefficients. By this, we mean that for each of the applicable limitations (or without), the problem is $NP$-Hard. The size notion is the sum, over all trees, of their number of nodes.

Theorem 2   It is $NP$-Hard to find the smallest weighted linear combinations of DT consistent with a set of examples $LS$, without limitation on the leveraging coefficients, or for any possible limitation, as long as at least one non-zero value is authorized.

While it is well known that boosting results in a rapid decreasing of the error over $LS$ which can easily and rapidly drop down to zero (as long as it is possible), Theorem 2 shows that attempts to efficiently reduce the size of the vote when boosting DT is $NP$-Hard. If the problem is simplified to the to pruning of a large consistent vote of DT [Margineantu Dietterich1997], to obtain a smaller consistent (or with limited error) vote with restricted size, it is again possible (using the same reduction) to show that this brings $NP$-Hardness.