2
$\begingroup$

I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size. Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$.

Now, assuming the fan in of each vertex is at most 2, I can set 2 bits for each vertex, one for the value of the vertex, and the other for which of his sons I am currently evaluating. Where I am stuck is that I am not given any information on the fan out of each vertex, So I can't just set a value to know which parent to go back to when I finish evaluating a sub circuit.

I would like some help understanding the catch here.

thanks.

$\endgroup$
  • 1
    $\begingroup$ Are you doing a depth-first search from the output? That's the right way to go. If you store the path from the output to your current vertex (1 left/right bit per vertex on the path) and a pointer to your current vertex, you can always go "1-up" by rewalking the path, starting from the output vertex. So you would have a pointer to your output vertex as well. And a third pointer that points to the current vertex while you're rewalking the path. $\endgroup$ – Albert Hendriks Apr 10 '18 at 20:33
  • $\begingroup$ Ah you mean go from the top to find the parent and check the value of the last son on the path? Yeah that's great! However, I don't think I can use a pointer to the output vertex as I am not given the size of the boolean circuit so the log of that can blow up the complexity. Can't I make an assumption on the input format? for example each depth level is in some sort of "brackets" and the children of the vertex on the level above also have some sort of mark, that way I can find my way in the circuit based only on the directional bits. (which of the 2 sons of a vertex in a level i am handling) $\endgroup$ – Eloo Apr 10 '18 at 20:53
1
$\begingroup$

This general question is captured by the concept of graph pebbling. Orient the edges of the circuit so that they point away from the leaves and toward the root. A pebbling of the graph is a series of moves, in the course of which pebbles are added to and removed from vertices (at most one pebble per vertex!), according to the following rules:

  • A pebble can always be removed.
  • A node $v$ can be pebbled (we can add a pebble to it) if all nodes $w$ such that there is an edge $w \to v$ are pebbled.

The goal is to pebble the root, and what we want to minimize is the maximum number of pebbles on the board. This minimum is called the pebbling number of the circuit.

If a circuit has pebbling number $p$, then it can be evaluated using roughly $p$ bits of memory. The idea is that pebbling a node corresponds to computing the its value, which is possible since all of its children are pebbled as well.

All of the above concerns the case in which the circuit is given ahead of time, and the goal is to construct a strategy to evaluate it on an unknown input. However, the same general approach can also be used to solve your problem, using the fact that the pebbling number of the complete binary tree of depth $D$ is $O(D)$. For more on pebbling, see Nordström's survey.

Finally, let me mention that the circuit evaluation problem is $\mathsf{P}$-complete. This means that assuming $\mathsf{L} \neq \mathsf{P}$, it is not possible to evaluate arbitrary circuit in logarithmic space. In contrast, the formula evaluation problem is in $\mathsf{ALOGTIME}$ (i.e., uniform $\mathsf{NC^1}$), and so in $\mathsf{L}$. This is due to important work of Buss.

$\endgroup$
  • $\begingroup$ Could you please explain why the method we talked about in the question and comments won't work? Can't I assume a certain format of the input, such that I can find a vertex based only on going left and from the root, assuming that the fan in is at most 2? $\endgroup$ – Eloo Apr 11 '18 at 9:25
  • $\begingroup$ The algorithm for pebbling a complete binary tree probably amounts to the same thing. $\endgroup$ – Yuval Filmus Apr 11 '18 at 11:13

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.