Question

There is the following theoretical computer science, namely:

For a particular monotone formula $M$ of size $n$, there's an equivalent formula of depth $\text{O}(\text{ln}\,n)$.

(I am reading the original paper in my library, if I have time later I will scan it and add scans of it to this post. My apologies for being unable to find a copy online.)

However, I'm finding myself going from step to step in the proof without really understanding what's going on, lacking intuition, as the paper is quite short and condensing quite a bit of reasoning and motivation, at least I feel. I was wondering if somebody could offer me their explanation of the proof of this result, hopefully with lots of their intuition thrown in so I and others reading can have a greater understanding of a proof?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top