Comparative Analysis of Deterministic and Nondeterministic Decision Tree Complexity. Local Approach

For problems with many-valued decisions over an arbitrary information system, we study the relations among the complexity of the problem description, the minimum complexity of a deterministic decision tree solving this problem, and the minimum complexity of a nondeterministic decision tree solving the problem. Rough classification of these relations is considered and all possible types of the relations are listed. This study was carried out within the frameworks of the local approach to the investigation of decision trees, where only attributes from a problem description are used for the construction of decision trees solving this problem.