The depth of decision trees for binary problems
Mikhail Moshkov · Moscow University Mathematics Bulletin · 2007
The depth of decision trees for binary problems (problems with decisions 0 or 1) over check systems from some class is studied in this paper. It is shown that if the number of checkings in the problem description in creases, then in the worst case the minimal depth of the decision tree solving the problem is either bounded from above by a constant, or inceeases almost as a logarithmic function, or increases like a linear function.