CVAL is in P (technical detail)

I would like to clarify to myself the way that an algorithm that proves the statement in the title works:

I think the idea should be like this:

1. We assign the input values to the bit nodes
2. We calculate the incoming edges values for each logical operator node
3. We finally get to the output node, and we have our result

What I would like to ask, is how technically we do step 2? I mean, it must be a sort of travel on the graph, where we visit each edge at most, let's say, 3 times, right?

Can the following implementation fit (even though it is not too formal)?

1. let VALUE(v) be the circuit value (for the input x) for the node v
2. if we know the values of the incoming edges of v we just compute the value of v
3. else: (assume the logical operator of v is *, and that the incoming edge comes from nodes v1,..,vn)
4. we return *(VALUE(v1),...VALUE(vn))

Yes, you are correct.

Essentially, since you are dealing with a circuit, the graph representing it is a DAG (directed acyclic graph). Hence, your implementation will indeed compute the value of each node, and will visit each node not a lot of times (usually it will be the "number of children$$+ 1$$", as in your recursive case), so it won't be hard to show this is indeed polynomial.

If you want to formally prove the fact that its polynomial, then here is a small hint: try to show why you need poly space first, then use that to your advantage when computing the time it takes to traverse on the graph.

• Great! thank you nir I got it.
• You are right that the total is the number of nodes (since there are no circles), but it can be possible that a lower-recursion-level does more recursive calls then a higher-recursion-level one. It doesn't really matter though - the only thing that matters is that each node is called a constant number of times (we implicitly assume a bounded fan-out). Since each node is called a constant number of times, and since the tape takes $poly(|C|)$ space (where $|C|$ is the number of nodes), the time to traverse takes $O(poly(|C|))$, and at each node you pay another $O(1)$ to compute the value Oct 19 '21 at 7:51
• sum everything up for all $|C|$ nodes and you will get $O(|C|\cdot poly(|C|))$ which is still polynomial Oct 19 '21 at 7:51