View article

We demonstrate that constructing optimal binary decision trees is an NP-complete problem, where an optimal tree is one which minimizes the expected num-ber of tests required to identify the unknown object. Precise definitions of NP-complete problems are given in refs.[1, 2, 4].

While the proof to be given is relatively simple, the importance of this result can be measured in terms of the large amount of effort that has been put into find-ing efficient algorithms for constructing optimal bi-nary decision trees (see [3, 5, 6] and their references). Thus at present we may conjecture that no such efficient algorithm exists (on the supposition that P¢ NP), thereby supplying motivation for finding efficient heuristics for constructing near~ optimal decision trees.