0
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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 .... $\endgroup$ – Bram28 Oct 10 '17 at 19:52
  • $\begingroup$ 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. $\endgroup$ – Fabio Somenzi Oct 11 '17 at 20:55
0
$\begingroup$

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$

Improve this answer
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Mees de Vries Oct 11 '17 at 9:03
  • $\begingroup$ @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. $\endgroup$ – Bram28 Oct 11 '17 at 9:35
  • $\begingroup$ 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. $\endgroup$ – Mees de Vries Oct 11 '17 at 11:12
  • $\begingroup$ @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? $\endgroup$ – Bram28 Oct 11 '17 at 11:21
  • $\begingroup$ I might, but can't for at least 23 hours. Or ask it on TCS stack exchange. $\endgroup$ – Mees de Vries Oct 11 '17 at 11:26

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.