2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.