1
$\begingroup$

I have seen it stated that if boolean function $f$ is computable by a $k$-CNF and an $l$-DNF then it can be computed by a decision tree of depth at most $kl$. However, I am not able to see why this is the case.

$\endgroup$

1 Answer 1

1
$\begingroup$

Observe that if a $k$-CNF $\Phi$ is equivalent to an $l$-DNF $\Psi$, then every term of $\Psi$ implies every clause of $\Phi$, i.e., they share a literal.

If the Boolean function is not constant, pick a clause $C$ in $\Phi$ and query all its variables. This is a decision tree of depth at most $k$. For each branch, restrict $\Phi$ and $\Psi$ by the partial assignment determined by the branch.

Each such restriction turns $\Psi$ into an $(l-1)$-DNF: if $D$ is any term of $\Psi$, let $x$ be a literal shared by $C$ and $D$; if $x$ is false, then $D$ is falsified, otherwise it is shortened by at least one literal.

Thus, the function becomes constant on each branch after at most $l$ iterations of this process.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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