Finding small equivalent decision trees is hard

DOI10.1142/S0129054100000193MaRDI QIDQ5249043zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hans Zantema, Hans L. Bodlaender

Publication date 29 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054100000193

zbMATH Keywords

decision treesNP-completenessBoolean functions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Minimization of decision trees is hard to approximate
• SIZES OF ORDERED DECISION TREES
• On the hardness of the minimum height decision tree problem
• Decision tree reduction
• Minimizing depth of decision trees with hypotheses

Cites work

• Constructing optimal binary decision trees is NP-complete
• Decision tree reduction
• Discrete decision theory: manipulations
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving the variable ordering of OBDDs is NP-complete

Cited in

(5)

• Decision tree approximations of Boolean functions
• On the hardness of the minimum height decision tree problem
• Properly learning decision trees in almost polynomial time
• Minimizing depth of decision trees with hypotheses
• Minimization of decision trees is hard to approximate

This page was built for publication: Finding small equivalent decision trees is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249043)