1
$\begingroup$

Notation: $|\alpha|$ denotes the length in characters of an expression $\alpha$ in propositional logic.

Consider Boolean decision trees which are in the form of complete binary trees whose leaves are all different propositional symbols written $p_i$ for some $i \in \mathbb{N}$. We are given that the $p_i$ are all independent from each other. Examples $\alpha_1$ and $\alpha_2$ are shown below. We observe that the $|\alpha_n|$ grow exponentially because the underlying complete binary trees grow exponentially.

$$ \alpha_1 = (a \land p_1) \lor (\lnot a \land p_2) $$

$$ \alpha_2 = (a \land ((b \land p_1) \lor (\lnot b \land p_2))) \lor (\lnot a \land ((b \land p_3) \lor (\lnot b \land p_4))) $$

Question: Is there any smaller equivalent form $\beta_n$ such that $\beta_n \leftrightarrow \alpha_n$ and the $\beta_n$ grow polynomially, that is, does there exist a $c$ such that $|\beta_n| = O(n^c)$?

I believe there are no such smaller $\beta_i$ for the following reasons:

  1. No two nodes in the binary tree can be merged since the $p_i$ are independent.
  2. No node can be deleted without creating an incorrect result.
$\endgroup$
5
  • 1
    $\begingroup$ That's a bit unclear. For example, $\neg(p_i \leftrightarrow p_j)$ is equivalent to $p_i \equiv \neg p_j$, and this can't be true for all $i \neq j$ unless you have at most two variables. Also, if leaves are propositional variables, and you don't repeat them, the tree has number of nodes linear in number of variables, not exponential. Your example looks more like you have a Boolean schema of some special form, and transform it to a formula - is it so? $\endgroup$
    – mihaild
    Sep 25 at 16:24
  • $\begingroup$ @mihaild: Thanks for writing. I tried to edit the question, but it won’t let me save the edits. You’re right about the equivalence problem, so the clause $\lnot (p_i \leftrightarrow p_j)$ is to be deleted. As for your other point, I should have included the fact that the number of variables $p_i$ equals $2^n$ for each $n$. $\endgroup$
    – ShyPerson
    Sep 25 at 16:58
  • $\begingroup$ @mihaild: As for the Boolean schema you ask about, the concept comes from the Mathematica function BooleanConvert, which has the option to convert any Boolean expression to a Boolean decision tree. You might need to expand the "Details and Options" section to view it; it's called BDT. $\endgroup$
    – ShyPerson
    Sep 25 at 17:26
  • 2
    $\begingroup$ The answer is no. Since any formula equivalent to $\alpha_n$ must contain each of the $2^n$ distinct variables $p_1$, $\dots$, $p_{2^n}$, it must have length at least $\Theta(2^n)$. $\endgroup$
    – David Moews
    Sep 25 at 17:45
  • $\begingroup$ @DavidMoews: Many thanks for writing. I would welcome your comment as an answer to this question. $\endgroup$
    – ShyPerson
    Sep 26 at 3:01

1 Answer 1

Reset to default
2
$\begingroup$

The answer is no. Since any formula equivalent to $\alpha_n$ must contain each of the $2^n$ distinct variables $p_1$, $\dots$, $p_{2^n}$, it must have length at least $2^n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .