2023/12/02 by Ostonov, Azimkhon, Moshkov, Mikhail
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.01116
In this paper, we consider classes of decision tables with many-valued decisions closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study a function H∞ψ,A(n) that characterizes the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that nondeterministic decision trees for a decision table can be interpreted as a way to represent an arbitrary system of true decision rules for this table that cover all rows. We indicate the condition for the function H∞ψ,A(n) to be defined everywhere. If this function is everywhere defined, then it is either bounded from above by a constant or is greater than or equal to n for infinitely many n. In particular, for any nondecreasing function φ such that φ(n)≥ n and φ(0)=0, the function H∞ψ,A(n) can grow between φ(n) and φ(n)+n. We indicate also conditions for the function H∞ψ,A(n) to be bounded from above by a polynomial on n.