  In this paper, we study arbitrary infinite binary information systems each of
which consists of an infinite set called universe and an infinite set of
two-valued functions (attributes) defined on the universe. We consider the
notion of a problem over information system which is described by a finite
number of attributes and a mapping corresponding a decision to each tuple of
attribute values. As algorithms for problem solving, we use deterministic and
nondeterministic decision trees. As time and space complexity, we study 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 almost as 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 five complexity
classes, and study for each class issues related to time-space trade-off for
decision trees.
