Finding small equivalent decision trees is hard

DOI10.1142/S0129054100000193zbMATH Open1319.68103DBLPjournals/ijfcs/ZantemaB00OpenAlexW2164916155WikidataQ59567937 ScholiaQ59567937MaRDI QIDQ5249043FDOQ5249043

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

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

zbMATH Keywords

decision treesNP-completenessBoolean functions

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

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

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)