Abstract
We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters characterizing both time (in the worst- and average-case) and space complexity of decision trees, i.e., depth, total path length (average depth), and number of nodes. We have created tools based on extensions of dynamic programming to study totally optimal trees. These tools are applicable to both exact and approximate decision trees, and allow us to make multi-stage optimization of decision trees relative to different parameters and to count the number of optimal trees. Based on the experimental results we have formulated the following hypotheses (and subsequently proved): for almost all Boolean functions there exist totally optimal decision trees (i) relative to the depth and number of nodes, and (ii) relative to the depth and average depth.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-13 |
| Number of pages | 13 |
| Journal | Discrete Applied Mathematics |
| Volume | 215 |
| DOIs | |
| State | Published - Jul 28 2016 |
Bibliographical note
KAUST Repository Item: Exported on 2020-10-01Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST). Authors acknowledge valuable comments and suggestions by anonymous reviewers that clearly improved the readability of this work and helped prove the two hypotheses.