# Least Depth Formula for Given Truth Table

Suppose I have $n$ propositional variables, $\{p_1,\ldots,p_n\}$ over which we truth tables and formulas over the language $\{\neg, \land, \lor, \top\}$. For the sake of this question, we define the depth of a formula by

• $\mathrm{depth}(p) = \mathrm{depth}(\top) = 0$,
• $\mathrm{depth}(\neg \phi) = \mathrm{depth}(\phi)$,
• $\mathrm{depth}(\phi \land \psi) = \mathrm{depth}(\phi \lor \psi) = 1 + \max(\mathrm{depth}(\phi), \mathrm{depth}(\psi))$.

I am interested in the question

What is the least integer $\chi(n)$ such that every truth table over $\{p_1,\ldots,p_n\}$ can be expressed with a formula of depth at most $\chi(n)$?

An easy upper bound is $\chi(n) = 2n - 2$, which we can show by induction. If $n = 1$ then the depth 0 formulas $p_1, \neg p_1, \top, \neg \top$ suffice. Inductively, given a truth table over $\{p_1,\ldots,p_n\}$, we split it in two: the part of the truth table where $p_n = 0$ and the part where $p_n = 1$. These then give us two formulas, $\phi_0, \phi_1$ in the variables $\{p_1,\ldots,p_{n-1}\}$, of depth at most $2n-4$. Then we can give our truth table via $(\phi_0 \land \neg p_n) \lor (\phi_1 \land p_n)$, which has depth $2n-2$.

My question is:

Is there a tighter bound on $\chi(n)$ than $2n-2$?

As a side note, I am also interested in bounding the length of the formula, rather than its depth, but that seems like a significantly more difficult question.

• My intuition is that $p_1 \oplus p_2 \oplus ... \oplus p_n$ requires a depth of at least 2n-2. ... not sure how to prove it .... – Bram28 Oct 10 '17 at 19:52
• An upper bound on $\chi(n)$ is $n - 1 + \log_2 n$. No function requires more than $2^{n-1}$ terms of $n$ variables in DNF (the parity function meets those bounds). Balanced trees have logarithmic depth. Of course, $(p_1 \oplus p_2 \oplus p_3 \oplus p_4)$ does not reach the upper bound, because the shallowest formula is not necessarily the one that comes from the DNF. – Fabio Somenzi Oct 11 '17 at 20:55

Proof Attempt: (EDIT: OK, so this does not work!!)

Let $mindepth(\varphi)$ be the minimum depth of all expressions able to capture $\varphi$.

Claim: The generalized XOR, i.e. $p_1 \oplus p_2 \oplus ... \oplus p_n$ can be expressed by an expression with a depth of $2n-2$, but not by one with a depth of less than $2n-2$. That is:

$$mindepth(p_1 \oplus p_2 \oplus ... \oplus p_n) = 2n-2$$

Correlary: $$\chi(n)=2n-2$$

Here's a proof by induction to show that $mindepth(p_1 \oplus p_2 \oplus ... \oplus p_n) = 2n-2$

Base: $n=1$. Then $p_1 \oplus p_2 \oplus ... \oplus p_n = p_1$, which can be expressed by $p_1$ itself, having a depth of $0$, and obviously you can't do better.. Check!

All-important observation:

$(p_1 \land \neg p_2) \lor (\neg p1 \lor p_2)$ as well as $(p_1 \lor p_2) \land (\neg p_1 \lor \neg p_2)$ both express $p_1 \oplus p_2$ with a depth of exactly $2$$. However, you cannot express$p_1 \oplus p_2$with an expression of depth less than$2$: Obviously neither of the$8$expressions with a depth of$0$($p_1$,$p_2$,$\neg p_1$,$\neg p_2$,$\bot$,$\neg \bot$,$\top$,$\neg \top$) will do, and neither will any of the expressions with a depth of$1$(there are$64$expressions combining any of the$8$0-depth expressions with any of the$8$0-depth expressions using a$\lor$, and another$64$using an$\land$, but none will capture$\oplus$(Proof By Exercise Left to Reader!)) Hence:$mindepth(p_1 \oplus p_2) = 2$What I hope to show is that: To express any$\varphi_1 \oplus \varphi_2$, where$\varphi_1$and$\varphi_2$are 'unrelated' will require an expression with a minimum depth of the sum of the minimum depths of$\varphi_1$and$\varphi_2$plus$2$. That is, for such$\varphi_1$and$\varphi_2$:$mindepth(\varphi_1 \oplus \varphi_2) = mindepth(\varphi_1) + mindepth(\varphi_2) + 2$OK, so let's assume by inductive hypothesis that$p_1 \oplus p_2 \oplus ... \oplus p_n$can be expressed by an expression with depth$2n-2$, but not by an expression with a depth smaller than$2n-2$. Now let's consider$p_1 \oplus p_2 \oplus ... \oplus p_{n+1}$. Then by the previous observation,$mindepth(p_1 \oplus p_2 \oplus ... \oplus p_{n+1})= mindepth(p_1 \oplus p_2 \oplus ... \oplus p_n) + mindepth(p_{n+1}+2 = 2n-2+0+2=2(n+1)-2$• If we let$\oplus$refer to the depth 2 formula for the two variable XOR, then we can make the four variable XOR as$(p_1 \oplus p_2) \oplus (p_3 \oplus p_4)$, which has depth$4 < 6$. – Mees de Vries Oct 11 '17 at 9:03 • @MeesdeVries Ah, very good! Thanks, actually, I knew my 'proof' had a lot of holes, and was wrecking my brain how to plug them, so now I can stop trying :) Well, this makes one suspect the formula has some kind of 2 log n in it, no? That is, my argument was assuming that you'd do something like$(((...(p_1\oplus p_2) \oplus p_3) \oplus p_4) ...)$and thus adding 2 to the depth for each additional variable, but you showed we can 'balance' that formula ... so with$n$between$5$and$8$we can construct formulas of depth$6$, etc. I still believe the generalized XOR is the 'worst' case though. – Bram28 Oct 11 '17 at 9:35 • I think a better candidate is the$n$-ary majority function$\mathrm{maj}_n$, where$\mathrm{maj}_n(p_1,\ldots,p_n)\$ is 1 if and only if the majority of its arguments is 1. But I don't know how I would go about proving that. – Mees de Vries Oct 11 '17 at 11:12
• @MeesdeVries Yeah, I can see that one would be nasty.... Well, this problem is indeed very tough, and unless inspiration hits me I think it's a little out of my league :( Maybe if no one else answers you could put a bounty on it? – Bram28 Oct 11 '17 at 11:21
• I might, but can't for at least 23 hours. Or ask it on TCS stack exchange. – Mees de Vries Oct 11 '17 at 11:26