1
$\begingroup$

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))
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Great! thank you nir I got it. $\endgroup$
    – e.ad
    Oct 19 at 6:06
  • $\begingroup$ As for the second part of your answer, I think I didn't manage to do that: I can't see how to use the fact of poly space to prove being belong to P, because the only relation I could think of now is that space(s(n)) is in time(2^s(n)), so by that I would need to prove that my algorithm needs LogSpace instead of Poly. $\endgroup$
    – e.ad
    Oct 19 at 6:08
  • $\begingroup$ And last thing, please correct me if i'm wrong here but the reason my algorithm needs poly-space is that the working-tape won't need to store more cells that the number of vertices (by a factor-constant). And I think the reason of that is that there are at most O(n) recursion calls at the first step, and except of that there is a constant work. And, as there are no circles in my graph, each lower-recursion-level MUST calls less times (because otherwise there are circles), to a total that the stack contains information as the number of nodes $\endgroup$
    – e.ad
    Oct 19 at 6:15
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Oct 19 at 7:51
  • $\begingroup$ sum everything up for all $|C|$ nodes and you will get $O(|C|\cdot poly(|C|))$ which is still polynomial $\endgroup$
    – nir shahar
    Oct 19 at 7:51

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.