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.
|Journal||International Journal of Foundations of Computer Science|
|Publication status||Published - 2000|