# Prove the following language is in L (LogSpace)

I'm trying to prove the following language is in $L$ (decided by a TM in $O(\log n)$ space):

$$A = \{ (C,x) \mid C(x)=1\text{ and C is a Boolean formula with depth }\log(n)\}\,,$$ where $n = |(C,x)|$. Equivalently, $C$ can be a Boolean circuit with maximum fan-out of $1$.)

Checking if a word $w$ is in "the right format" (meaning: $w=(C,x)$ for some $C$ Boolean formula/circuit, $x$ – input) takes $O(1)$ space. I'm not sure on how to check the value of the formula (thought of using recursion, but not sure how) such that it will need only $O(\log n)$ space. Also, how can I check that the depth of the circuit is $\log n$?

• A much harder result, due to Sam Buss, gives a logspace algorithm for evaluating an arbitrary Boolean formula. – Yuval Filmus Feb 7 '17 at 13:03
• – user12859 Feb 7 '17 at 14:35

When at a $\lor$ gate with a previous value $b$: If $b = 0$ leave the value the same and go to the node's parent. If $b = 1$ check the other (right) son. Same with $\land$ gate, and $\lnot$ gates are easier (check if $b = 0$). Accept $(C, x)$ if the value computed by $C$ (using the in-order search) is $1$.
Saving the current node takes $\log n$ bits, the current value takes $1$ bit and computing the parent also takes $\log n$. Overall there is a TM that uses $O(\log n)$ space that decides $A$, so $A \in L$.