Finding small equivalent decision trees is hard

    Research output: Contribution to journalArticleAcademicpeer-review

    29 Citations (Scopus)
    4 Downloads (Pure)

    Abstract

    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
    Volume11
    Issue number2
    DOIs
    Publication statusPublished - 2000

    Fingerprint

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

    Cite this