Finding small equivalent decision trees is hard

H. Zantema, H.L. Bodlaender

    Research output: Contribution to journalArticleAcademicpeer-review

    41 Citations (Scopus)
    4 Downloads (Pure)


    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.
    Original languageEnglish
    Pages (from-to)343-354
    JournalInternational Journal of Foundations of Computer Science
    Issue number2
    Publication statusPublished - 2000


    Dive into the research topics of 'Finding small equivalent decision trees is hard'. Together they form a unique fingerprint.

    Cite this