Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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))$.
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)}$.
Not sure what you mean by "number of leaves in a decision tree", as the decision tree is usually a full tree. If you mean the number of nodes in a BDD (where you can essentially omit unnecessary tests), then I'm pretty sure you can construct a BDD that is at most the size of a DNF formula - simply test each clause "separately" (i.e. on a different branch), this can take at most the length of the DNF representation.
