I've been having hard time with proving the following claim:Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the number of leaves) decision tree for $f$. Also, let $size_{CNF}(f),size_{DNF}(f)$ denote the number of clauses, terms in the minimal $CNF,DNF$ formulas for $f$ respectively.Prove that $size_{DT}(f)\in poly(n,size_{DNF}(f),size_{CNF}(f))$.
Size of decision tree for f is polynomial in the DNF size of f and CNF size of f
cc.complexity theory;machine learning;boolean functions;combinatory logic;boolean formulas