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.


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.