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.
翻译:在本文中,我们研究任意的无限的二进制信息系统,其中每个系统都由宇宙和宇宙定义的一套两值功能(属性)的无限集合组成。我们考虑信息系统上的问题概念,由数量有限的属性和对每个属性的映射来描述。作为解决问题的算法,我们使用确定性和非确定性决定树。作为时间和空间的复杂性,我们研究决定树中的节点的深度和数量。最坏的情况是,随着问题描述中属性数量的增加,(一) 确定性决定性树的最低深度几乎是对数或线性增长,(二) 非确定性决定性决定树的最低深度,要么是常数或线性增长,(三) 确定性决定树的最小节点数量,要么是多度增长,要么是指数增长,(四) 非确定性决定性决定树的最小节点数量,要么是多度增长,要么是指数增长,要么是指数增长。根据这些结果,(二) 非确定性决定性决定树的最小深度,从上面的深度或线性决定树的最小深度,(五级),我们为有关决定的顺序的每个交易系统设定了相关的五级,我们将所有决定的固定的顺序的顺序和每一轮时间序列的复杂程度。