The depth of decision trees for binary problems

Research output: Contribution to journalArticlepeer-review

Abstract

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 languageEnglish (US)
Pages (from-to)108-111
Number of pages4
JournalMoscow University Mathematics Bulletin
Volume62
Issue number3
DOIs
StatePublished - Jun 2007
Externally publishedYes

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The depth of decision trees for binary problems'. Together they form a unique fingerprint.

Cite this