The problem of learning an optimal decision tree is known to be NP-complete under several aspects of optimality and even for simple concepts.
הבעיה בלמידת עץ החלטות אופטימלי ידועה כ-NP-complete תחת כמה היבטים של אופטימלי ואפילו במושגים פשוטים.