27
$\begingroup$

I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.

A Boolean circuit is called an NC0k circuit if each output gate syntactically depends on at most k input gates. (We say that an output gate g syntactically depends on an input gate g′ when there is a directed path from g′ to g in the circuit as viewed as a directed acyclic graph.)

In the aforementioned question, QiCheng asked about the complexity of the following problem, where k is a constant:

Instance: An NC0k circuit with n-bit input and n-bit output.
Question: Does the given circuit compute a permutation on {0, 1}n? In other words, is the function computed by the circuit a bijection from {0, 1}n to {0, 1}n?

As Kaveh commented on that question, it is easy to see that the problem is in coNP. In an answer, I showed that the problem is coNP-complete for k=5 and that it is in P for k=2.

Question. What is the complexity for k=3?

Clarification on May 29, 2013: “A permutation on {0, 1}n” means a bijective mapping from {0, 1}n to itself. In other words, the problem asks whether every n-bit string is the output of the given circuit for some n-bit input string.

$\endgroup$
  • 1
    $\begingroup$ Personal note: When I posted an answer to QiCheng’s question, I did so just because the problem looked interesting, without any particular application in mind. Several months after that, I happened to be in a situation where I had to explain to someone that it is far from trivial to decide whether a given program computes a permutation or not. Thanks to QiCheng’s question, I had a perfect example (what a coincidence!). After that, I became more curious about the cases of k=3 and k=4. I suspect that the case of k=3 is already coNP-complete, but I have not been able to prove either way. $\endgroup$ – Tsuyoshi Ito Aug 26 '12 at 16:42
  • $\begingroup$ this problem seems to be a particular case of the Pigeonhole Circuit problem defined by Papadimitriou (sciencedirect.com/science/article/pii/S0022000005800637) which is complete for PPP with respect to poly-time reductions between search problems. $\endgroup$ – Marcos Villagra Jul 3 '13 at 3:31
  • $\begingroup$ @Marcos Villagra: Thank you for the comment, but I am afraid that by saying “particular case of,” you are changing the definition of the Pigeonhole Circuit problem significantly. An important property of the Pigeonhole Circuit problem is that it is a total search problem, whereas the current problem (viewed as a search problem for two inputs which produce the same output) is not a total search problem. $\endgroup$ – Tsuyoshi Ito Jul 3 '13 at 23:56
3
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

Not the answer the author was seeking, see comments that clarify what "permutation" is in this context.

I cranked out the size of the minimum dominating set for the monogenic permutation group inclusion digraph: https://oeis.org/A186202

All you have to do is test one member of every prime cycle decomposition.

For each prime cycle it should be sufficent to code the elements as (10101010...), then (01010101..)?

------Clarification------ The goal of this approach is to model your 2^n test cases as a digraph. If one sucessful test case implies another sucessful test case, then you only have to test the min dominating set of this test space digraph. In the space of permutations OEIS A186202 is the max you have to test to either detect a non-trivial subgroup or prove none exist; this number is still large but much smaller than n!.

--Musing-- By using n-1 zeros and 1 one in n iterations you can detect the fixed permutation you are looking for. After that in O( n{(n-1) \choose (k-1)}(2^(k-1)) you can test that every set of (k-1) variables does not effect each index of the shuffle. Since k is fixed that is polynomial. Am I missing something?

$\endgroup$
  • $\begingroup$ Hmm. Not sure if the (01)*, (10)* is sufficent. You might have to try all 2^p configurations for each prime cycle. $\endgroup$ – Chad Brewbaker May 24 '13 at 21:42
  • 2
    $\begingroup$ Sorry, Chad, you lost me. You are aware that the question is asking whether the function is bijective? (There are $(2^n)!$ such bijective functions.) It is not asking whether the output bits are a permutation (re-ordering) of the input bits -- that's a much easier problem, which can be answered simply by running the circuit on all possible inputs with $n-1$ zeros and $1$ one. $\endgroup$ – D.W. May 28 '13 at 3:56
  • 2
    $\begingroup$ Chad, yes, I believe you might be missing something. The poster is asking whether the function $C:\{0,1\}^n \to \{0,1\}^n$ is a bijective function (i.e., there does not exist $x,x' \in \{0,1\}^n$ such that $C(x)=C(x')$ and $x \ne x'$). He/she is not asking whether the function $C$ permutes (shuffles/re-arranges/re-orders) the input bits. Do you see the difference? I suspect you've been answering the wrong question. $\endgroup$ – D.W. May 28 '13 at 16:05
  • 2
    $\begingroup$ Thank you for trying to help, but as D.W. explained, I am afraid that the question you answered is different from the one I asked. “A permutation on {0,1}^n” means a bijective function from {0,1}^n to itself, and it does not mean rearranging the n bits. $\endgroup$ – Tsuyoshi Ito May 29 '13 at 14:16
  • 3
    $\begingroup$ Chad, would you mind deleting this answer or at least adding a note to the top that this is not answering Tsuyoshi's question? $\endgroup$ – Kaveh Jun 29 '13 at 7:02

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.