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 increases, then in the worst case the minimal depth of the decision tree solving the problem is either bounded from above by a constant, or increases almost as a logarithmic function, or increases like a linear function.
|Original language||English (US)|
|Number of pages||4|
|Journal||Moscow University Mathematics Bulletin|
|State||Published - Jun 2007|
ASJC Scopus subject areas