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 , 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 -Hard. The size notion is the sum, over all trees, of their number of nodes.