2
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

A Boolean formula is a circuit whose graph is a tree (each node has a single parent). Perform an in-order pass on the tree while remembering the current node and the last value.

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$.

$\endgroup$

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.