Complexity of Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables From Closed Classes

This paper investigates classes of decision tables (DTs) with 0-1-decisions that are closed under the removal of attributes (columns) and changes to the assigned decisions to rows. For tables from any closed class (CC), the authors examine how the minimum complexity of deterministic decision trees (DDTs) depends on the minimum complexity of a strongly nondeterministic decision tree (SNDDT). Let this dependence be described with the function F-psi A ( n ). The paper establishes a condition under which the function F-psi A ( n ) can be defined for all values. Assuming F-psi A ( n ) is defined everywhere, the paper proved that this function exhibits one of two behaviors: it is bounded above by a constant or it is at least n for infinitely many values of n . In particular, the function F-psi A ( n ) can grow as an arbitrary nondecreasing function phi ( n ) that satisfies phi ( n ) >= n and phi (0) = 0. The paper also provided conditions under which the function F-psi A ( n ) remains bounded from above by a polynomial in n .