Comparative Analysis of Deterministic and Nondeterministic Decision Tree Complexity. Global 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 global approach to the investigation of decision trees, where arbitrary attributes from the information system can be used for the construction of decision trees solving problems.