Time and Space Complexity of Deterministic and Nondeterministic Decision Trees. Local Approach

For conventional problems over an arbitrary infinite binary information system, we study relations between time and space complexity of deterministic and nondeterministic decision trees solving these problems and using only attributes from the problem descriptions. As time and space complexity, we consider the depth and the number of nodes in the decision trees. In the worst case, with the growth of the number of attributes in the problem description, (i) the minimum depth of deterministic decision trees grows either as a logarithm or linearly, (ii) the minimum depth of nondeterministic decision trees either is bounded from above by a constant or grows linearly, (iii) the minimum number of nodes in deterministic decision trees has either polynomial or exponential growth, and (iv) the minimum number of nodes in nondeterministic decision trees has either polynomial or exponential growth. Based on these results, we divide the set of all infinite binary information systems into three complexity classes, and study for each class issues related to time-space trade-off for decision trees.