<p>The definition of Boolean circuit used in the paper is given (rather succinctly) inside the proof of the first theorem as a finite sequence of instructions of the form</p>
<pre><code>z = OP(y_1,...,y_n)
</code></pre>
<p>where OP is either AND (with n=2), NOT (with n=1) or nothing at all (in which case the right hand side is just an input x_i of the circuit), z is a new variable and y_1,...,y_n are variables defined by previous instructions.  The paper doesn't say so but this way of representing circuits is sometimes referred to as <em>straight-line programs</em> (maybe this terminology was introduced after 1977).</p>
<p>The reduction from CIRCUIT VALUE to PLANAR CIRCUIT VALUE described in the paper takes a straight-line program and transforms it to an equivalent planar straight-line program.  The output of the transformation is described in graphical form (as an &quot;actual&quot; circuit) but it is obvious how to recover the straight-line program from it.</p>
<p>To understand the transformation, think of the <span class="math-container">$k$</span>-th instruction of a straight-line program as a little circuit <span class="math-container">$C_k$</span> with <span class="math-container">$k-1$</span> inputs, <span class="math-container">$k$</span> outputs and just one gate <span class="math-container">$g$</span> of suitable type (AND, NOT, input).  The inputs of <span class="math-container">$C_k$</span> corresponding to the inputs of <span class="math-container">$g$</span> are duplicated: one copy is given as input to <span class="math-container">$g$</span> and the other copy as output of <span class="math-container">$C_k$</span> so that they may be re-used by later instructions.  The output of <span class="math-container">$g$</span> is the <span class="math-container">$k$</span>-th output of <span class="math-container">$C_k$</span>.</p>
<p>In general, you will need permutations to implement <span class="math-container">$C_k$</span>.  For example, in case <span class="math-container">$g$</span> is an AND gate, one may assume that the inputs of <span class="math-container">$g$</span> are the <span class="math-container">$i$</span>-th and <span class="math-container">$j$</span>-th inputs of <span class="math-container">$C_k$</span> with <span class="math-container">$i&lt;j$</span>, so <span class="math-container">$C_k$</span> may be described as follows:</p>
<ul>
<li>apply a permutation bringing <span class="math-container">$i$</span> to position <span class="math-container">$j-1$</span>;</li>
<li>apply <span class="math-container">$g$</span> to <span class="math-container">$j-1$</span> and <span class="math-container">$j$</span>;</li>
<li>apply a permutation bringing position <span class="math-container">$j-1$</span> back to <span class="math-container">$i$</span> and the output of <span class="math-container">$g$</span> to position <span class="math-container">$k$</span>.</li>
</ul>
<p>The paper shows that these permutations may be implemented by planar circuits, using the planar &quot;cross over&quot; circuit shown at the beginning of p.27.  The reduction then simply takes each line of a straight-line program, seen as a little circuit as above, and implements it as a planar circuit.  Composition of planar circuits is planar, so we're fine.  That the reduction may be computed in logspace is obvious.</p>
<p>The reduction is illustrated with an example at the beginning of p.28, in which it is assumed that <span class="math-container">$C_6$</span> (the little circuit corresponding to the sixth instruction of the straight-line program) contains an AND gate whose inputs are the 1st and 4th inputs of <span class="math-container">$C_6$</span>.</p>

CC BY-SA 4.0
2024-05-12T08:38:54.170Z
2024-05-12T08:38:54.170Z
Damiano Mazza
<p>In <a href="https://dl.acm.org/doi/pdf/10.1145/1008354.1008356" rel="nofollow noreferrer">https://dl.acm.org/doi/pdf/10.1145/1008354.1008356</a>, a proof is given for PCV is log space complete. I do not understand the construction though, a circuit is given but it is not clear to me what is happening and I don't see how it can be correct. Is it describing such that fanin 2 nodes are converted to AND gates? I'm not following the example or the explanation.</p>

<circuit-complexity>
planar circuit logspace completeness
redrobinyum
# planar circuit logspace completeness

(Asked by: username_0 on 2024-05-10)

In <https://dl.acm.org/doi/pdf/10.1145/1008354.1008356>, a proof is given for PCV is log space complete. I do not understand the construction though, a circuit is given but it is not clear to me what is happening and I don't see how it can be correct. Is it describing such that fanin 2 nodes are converted to AND gates? I'm not following the example or the explanation.

**Tags:** circuit-complexity


---

## 1 answers

### Answer by username_1 on 2024-05-12. Score: 2

The definition of Boolean circuit used in the paper is given (rather succinctly) inside the proof of the first theorem as a finite sequence of instructions of the form
z = OP(y_1,...,y_n)

where OP is either AND (with n=2), NOT (with n=1) or nothing at all (in which case the right hand side is just an input x_i of the circuit), z is a new variable and y_1,...,y_n are variables defined by previous instructions.  The paper doesn't say so but this way of representing circuits is sometimes referred to as straight-line programs (maybe this terminology was introduced after 1977).
The reduction from CIRCUIT VALUE to PLANAR CIRCUIT VALUE described in the paper takes a straight-line program and transforms it to an equivalent planar straight-line program.  The output of the transformation is described in graphical form (as an "actual" circuit) but it is obvious how to recover the straight-line program from it.
To understand the transformation, think of the $k$-th instruction of a straight-line program as a little circuit $C_k$ with $k-1$ inputs, $k$ outputs and just one gate $g$ of suitable type (AND, NOT, input).  The inputs of $C_k$ corresponding to the inputs of $g$ are duplicated: one copy is given as input to $g$ and the other copy as output of $C_k$ so that they may be re-used by later instructions.  The output of $g$ is the $k$-th output of $C_k$.
In general, you will need permutations to implement $C_k$.  For example, in case $g$ is an AND gate, one may assume that the inputs of $g$ are the $i$-th and $j$-th inputs of $C_k$ with $i, so $C_k$ may be described as follows:

apply a permutation bringing $i$ to position $j-1$;
apply $g$ to $j-1$ and $j$;
apply a permutation bringing position $j-1$ back to $i$ and the output of $g$ to position $k$.

The paper shows that these permutations may be implemented by planar circuits, using the planar "cross over" circuit shown at the beginning of p.27.  The reduction then simply takes each line of a straight-line program, seen as a little circuit as above, and implements it as a planar circuit.  Composition of planar circuits is planar, so we're fine.  That the reduction may be computed in logspace is obvious.
The reduction is illustrated with an example at the beginning of p.28, in which it is assumed that $C_6$ (the little circuit corresponding to the sixth instruction of the straight-line program) contains an AND gate whose inputs are the 1st and 4th inputs of $C_6$.


---

