# Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

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))$.

• I just learned that this claim is incorrect, check: lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.ps Feb 16 '13 at 11:15
• It would be good to that as an answer and explain why it answers your question a bit more. Mar 18 '13 at 16:54

As pointed out by the OP (user13772), this is false. Jukna et al. constructed explicit Boolean functions $f$ that require deterministic decision trees of size $2^{\Omega(\log^2 N)}$, where $N$ is the number of monomials in a minimal DNF for $f$ and $\lnot f$. Note that every Boolean function on $n$ inputs can be expressed as a deterministic decision tree of size $2^{O(\log n \log^2 N)}$.
• S. Jukna, A. Razborov, P. Savický, I. Wegener, On P versus NP$\cap$co-NP for decision trees and read-once branching programs, Computational Complexity 8 (1999), 357–370. doi:10.1007/s000370050005 (preprint)