This problem with $k=3$ is coNP-hard (and therefore coNP-complete).
To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a non-bijective function).
First a preliminary definition that will be helpful:
We define a labeled graph to be a directed graph, some of whose edges are labeled with literals, with the property that every vertex has either one unlabeled incoming edge, one labeled incoming edge, or two unlabeled incoming edges.
The reduction
Suppose we have a 3-SAT formula $\phi$ consisting of $m$ clauses, each containing three literals. The first step is to construct a labeled graph $G$ from $\phi$. This labeled graph contains one copy of the following gadget (sorry for the terrible diagram) for each clause in $\phi$. The three edges labeled L1, L2, and L3 are instead labeled with the literals in the clause.
|
| |
| |
| O<-----\
| ^ |
| | |
| | |
| /----->O |
| | ^ |
| | | |
| | | |
| O O O
| ^ ^ ^
| | | |
| |L1 |L2 |L3
| | | |
| O O O
| ^ ^ ^
| | | |
| | | |
| \------O------/
| ^
| |
| |
| O
| ^
| |
|
The gadgets (one for each clause) are all arrange in one big cycle with the bottom of one gadget linking to the top of the next.
Note that this arrangement of gadgets does in fact form a labeled graph (every vertex has indegree 1 or 2 with only edges leading to vertices of indegree 1 being labeled).
From the formula $\phi$ and the labeled graph $G$ (which was constructed from $\phi$) we next construct an $NC_3^0$ circuit (this will conclude the reduction). The number of inputs and outputs for this circuit is $n+v$ where $n$ is the number of variables in $\phi$ and $v$ is the number of vertices in $G$. One input and one output is assigned to each variable in $\phi$ and to each vertex in $G$. If $x$ is some variable in $\phi$ then we will refer to the input and output bits associated with $x$ as $x_{in}$ and $x_{out}$. Furthermore, if $l$ is a literal with $l = x$ then we define $l_{in} = x_{in}$ and if $l$ is a literal with $l = \neg x$ then we define $l_{in} = \neg x_{in}$. Finally, if $v$ is some vertex in $G$ then we will refer to the input and output bits associated with $v$ as $v_{in}$ and $v_{out}$.
There are four types of output bits:
1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Note that this output depends on only one input bit.
2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Note that this output depends on only two input bits.
3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l_{in})$. Note that this output depends on only three input bits since $l_{in}$ depends only on $x_{in}$ for whatever variable $x$ is used in the literal $l$.
4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. Note that this output depends on only three input bits.
Since in all cases the output depends on only three inputs, the circuit we build is in $NC_3^0$ as desired.
Correctness proof case 1: $\phi$ is satisfiable
Suppose there exists a satisfying assignment for $\phi$. Then construct the following two sets of values for the inputs.
1) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. All of the inputs associated with vertices of $G$ are given the value 0.
2) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. Consider the vertices in one clause gadget in $G$. If the value of a label is 0 (under the satisfying assignment), the input associated with the vertex at the target endpoint of the edge labeled with that label is given a value of 0. If both L1 and L2 have value 0 then the second-top vertex in the gadget (as shown above) is also given a value of 0. All other vertices are given a value of 1.
We wish to show that these two sets of inputs yield identical outputs and therefore that the $NC_3^0$ circuit does not encode a permutation.
Consider the four types of output bits:
1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Since $x_{in}$ is the same for both sets of inputs, outputs of this form will always be the same across the two sets of inputs.
2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Examining the gadget whose copies make up $G$, we see that all such edges consist only of pairs of vertices whose input values are always 1s under the second set of inputs. Thus $v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$ under the first set of inputs and $v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$ under the second set of inputs. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.
3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l)$. If $l$ is false under the assignment then $v_{in}$ is 0 under both sets of inputs; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$ under both sets of inputs. If $l$ is true under the assignment, $v_{in}$ is 0 under the first set of inputs and 1 under the second; also note that in the gadget, the only labeled edges $(u, v)$ have vertices $u$ which always have $u_{in} = 1$ under the second set of inputs. As a result we see that under both sets of inputs, $u_{in} = v_{in}$ whenever $l$ is true; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.
4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. There are two such vertices in each gadget. The top vertex and the second-from top vertex. We consider those two cases separately.
4a) When $v$ is the second-top vertex in a gadget, $u$ and $w$ are the two target endpoints of the edges labeled L1 and L2. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff L1 has value 0 under the satisfying assignment (aka $u_{in} = L1$); similarly, $w_{in}$ is 0 iff L2 has value 0 under the satisfying assignment (aka $w_{in} = L2$); and finally, $v_{in}$ is defined to be 0 iff both L1 and L2 have value 0 (aka $v_{in} = L1 \lor L2$). Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.
4b) When $v$ is the top vertex in a gadget, $u$ is the second-top vertex and $w$ is the target endpoint of the edge labeled L3. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff both L1 and L2 have value 0 (aka $u_{in} = L1 \lor L2$); $w_{in}$ is 0 iff L3 has value 0 (aka $w_{in} = L3$); and finally $v_{in} = 1$. Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$ where the equality $(L1 \lor L2 \lor L3) = 1$ holds by definition in a satisfying assignment for every clause. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.
Clearly, we see that the outputs are the same for two different sets of inputs and therefore that the $NC_3^0$ circuit enacts a non-bijective function.
Correctness proof case 2: $\phi$ is unsatisfiable
Suppose now that there exists no satisfying assignment for $\phi$. Then assume for the sake of contradiction that some two different sets of inputs lead to the $NC_3^0$ circuit having the same output.
Clearly, the two inputs must have the same values for $x_{in}$ for every variable $x$ in $\phi$. Thus we may now unambiguously refer to the value of $x$.
Define $S$ to be the set of vertices $v$ in $G$ such that $v_{in}$ is different in the two sets of input values.
We will prove the following lemmas below:
Lemma 1: If in some gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertices above those three in the gadget are in $S$.
Lemma 2: If in some gadget the top vertex is not in $S$ then in the next gadget up no vertex is in $S$.
Since the gadgets form a loop, this implies that if in any gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertex in $G$ is in $S$ (in other words $S$ is empty).
However, consider a gadget associated with a clause $(L1 \lor L2 \lor L3)$ that is not satisfied. In this gadget all three labels have value 0. We know that edge $(u, v)$ labeled $L$ must satisfy $v_{out} = v_{in} \oplus (u_{in} \land L)$, but $L = 0$, so $v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$. Thus since the output is the same for both inputs, the values of $v_{in}$ must also be the same across the two sets of inputs. In other words, we have shown that $v$ is not in $S$. Thus we see that in this particular gadget, the three vertices at the target endpoints of the labeled edges are not in $S$.
As a result, we conclude that $S$ is empty. This however, implies that between the two sets of inputs, there were no differences, which contradicts the assumption that these input sets are different. As a result, we see that the function enacted by the $NC_3^0$ circuit is injective and therefore a bijection.
All that's left is to prove the lemmas.
To do this, we note that for every type of vertex in $G$ (indegree 1 with label, indegree 1 without label, and indegree 2), if all incoming edges come from vertices not in $S$ then the vertex in question is also not in $S$. This is because in all three cases $v_{out} = v_{in} \oplus X$ where $X$ is some function of the inputs associated with variables and/or vertices with edges to $v$. Since all such vertices are not in $S$ by assumption, the value of $X$ must be the same under both sets of inputs. Therefore $v_{in} = v_{out} \oplus X$ is also the same under both sets of inputs. In other words $v$ is not in $S$.
Now that we have the rule that a vertex is not in $S$ whenever all of its predecessors are not in $S$, the lemmas follow simply by applying the rule repeatedly to the gadget diagram above.
