Finding small equivalent decision trees is hard

Two decision trees are called decision equivalent if they represent the same function, i.e., they yield the same result for every possible input. We prove that given a decision tree and a number, to decide if there is a decision equivalent decision tree of size at most that number is NPcomplete. As a consequence, nding a decision tree of minimal size that is decision equivalent to a given decision tree is an NP-hard problem. This result diers from the well-known result of NP-hardness of nding a decision tree of minimal size that is consistent with a given training set. Instead our result is a basic result for decision trees, apart from the setting of inductive inference.