<h3>Hardness</h3>

<p>Following your comment on the question, we will call a circuit where each output bit depends on at most <i>k</i> input bits a “NC<sup>0</sup><sub><i>k</i></sub> circuit.”  Using this term, your problem is coNP-complete in case of NC<sup>0</sup><sub>5</sub> circuits.  That is, the following problem is coNP-complete.</p>

<p><em>Instance</em>: A Boolean circuit <i>C</i> with <i>n</i> input bits and <i>n</i> output bits where each output bit depends on at most five input bits.<br>
<em>Question</em>: Is the mapping from {0,1}<sup><i>n</i></sup> to itself computed by <i>C</i> bijective?</p>

<p>As Kaveh commented, it is clearly in coNP, even without the bound on the number of input bits on which each output bit depends.  To prove the coNP-hardness, we will reduce 3SAT to the complement of the current problem.  The key idea of the reduction is the same as the one used in the paper [Dur94] by Durand, which I mentioned in a comment on the question, but the whole reduction is much simpler in our case.</p>

<p>Given a 3CNF formula <i>φ</i> with <i>n</i> variables and <i>m</i> clauses, we construct a Boolean circuit <i>C</i> with (<i>n</i>+<i>m</i>) input bits and (<i>n</i>+<i>m</i>) output bits as follows.  We label the input bits as <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub>, <i>y</i><sub>1</sub>, …, <i>y</i><sub><i>m</i></sub>, and the output bits as <i>x</i>′<sub>1</sub>, …, <i>x</i>′<sub><i>n</i></sub>, <i>z</i><sub>1</sub>, …, <i>z</i><sub><i>m</i></sub>.  We consider that the input bits <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> specify a truth assignment to the <i>n</i> variables in <i>φ</i>.</p>

<ul>
<li><i>x</i>′<sub><i>i</i></sub> = <i>x</i><sub><i>i</i></sub> for 1≤<i>i</i>≤<i>n</i>.  That is, the first <i>n</i> bits of input are always copied to the first <i>n</i> bits of output.</li>
<li>For 1≤<i>i</i>≤<i>m</i>, if the <i>i</i>th clause of <i>φ</i> is satisfied, then <i>z</i><sub><i>i</i></sub> = <i>y</i><sub><i>i</i></sub> ⊕ <i>y</i><sub><i>i</i>+1</sub>, where the subscript is interpreted modulo <i>m</i>.  Otherwise, <i>z</i><sub><i>i</i></sub> = <i>y</i><sub><i>i</i></sub>.</li>
</ul>

<p>Note that each output bit depends on at most five input bits.  I omit the proof of the correctness of the reduction, but the key idea (which I borrowed from [Dur94]) is that if <i>φ</i> is satisfiable and input bits <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> are set to a satisfying assignment of <i>φ</i>, then the <i>m</i> output bits <i>z</i><sub>1</sub>, …, <i>z</i><sub><i>m</i></sub> are constrained to have the even parity, and therefore the circuit cannot be a permutation.  On the other hand, if input bits <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>n</i></sub> are set to a non-satisfying assignment of <i>φ</i>, then output bits <i>z</i><sub>1</sub>, …, <i>z</i><sub><i>m</i></sub> can be set to anything; because of this, if <i>φ</i> is unsatisfiable, then the circuit is a permutation.</p>

<h3>Tractability</h3>

<p>On the tractable side, your problem is in P in case of NC<sup>0</sup><sub>2</sub> circuits.  This is shown as follows.  In general, each output bit in a Boolean circuit for a permutation is <em>balanced</em>; i.e., exactly half of the input strings set the output bit to 1.  However, every balanced Boolean function from {0,1}<sup>2</sup> to {0,1} is <em>affine</em>; i.e., a copy of a single input bit, the XOR of the two input bits, or the negation of them.  Therefore, we can first check that each output bit is balanced, and then check the bijectivity by the Gaussian elimination.</p>

<p>I do not know the complexity in case of NC<sup>0</sup><sub>3</sub> circuits or in case of NC<sup>0</sup><sub>4</sub> circuits.</p>

<h3>References</h3>

<p>[Dur94] Bruno Durand.  Inversion of 2D cellular automata: some complexity results.  <em>Theoretical Computer Science</em>, 134(2):387–401, Nov. 1994.  DOI: <a href="http://dx.doi.org/10.1016/0304-3975%2894%2990244-5">10.1016/0304-3975(94)90244-5</a>.</p>

CC BY-SA 3.0
2012-08-19T20:44:46.593Z
I posted a [follow-up question](http://cstheory.stackexchange.com/questions/12351/deciding-whether-an-nc0-3-circuit-computes-a-permutation-or-not) about the case of NC^0_3 circuits.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-22T22:41:20.823Z
2011-10-23T10:33:19.930Z
2011-10-23T10:33:19.930Z
Tsuyoshi Ito
<p>What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit
with $n$ input bits and $n$ output bits computes  a permutation 
of $\{0,1\}^n$? in the other words, whether every bit strings in 
$\{0,1\}^n$ is an output of the circuit for some input?
It looks like a problem which has been studied, 
but I cannot find any references.</p>

CC BY-SA 3.0
2011-10-20T07:18:27.033Z
The obvious bound is $\mathsf{coNP}$ which also works for $\mathsf{P}$ (check if the function is injective).
Kaveh
CC BY-SA 3.0
2011-10-20T14:18:57.933Z
What do you mean by “an NC0 circuit”?  The usual phrase is “NC0 family of circuits,” which is (perhaps unfortunately) often abbreviated to “NC0 circuit,” but I do not think that you mean an NC0 family of circuits in your question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-20T18:32:06.817Z
By an $NC^0$ circuit, I mean that every output bit of the circuit depends only on constant number of input bits.
QiCheng
CC BY-SA 3.0
2011-10-21T15:02:50.310Z
Every output in *every* circuit depends only on constant number of input bits. Circuits classes like $\mathsf{NC^0}$ only make sense when we consider circuits families. Do you mean that there is a fixed value $d$ and we only consider circuits of that fixed depth $d$?
Kaveh
CC BY-SA 3.0
2011-10-21T16:47:52.327Z
Yes I am asking about a family. To make things more clear, you can change $NC^0$ to $NC_5^0$ where every output bit depends only on $5$ input bits in the family.
QiCheng
CC BY-SA 3.0
2011-10-22T22:10:37.390Z
This does not answer your question, but if the problem is generalized so that each output bit is allowed to depend on O(log n) input bits, then I think that the problem is coNP-complete under Turing reducibility.  This follows from the coNP-completeness of the finite reversibility of two-dimensional cellular automata ([Durand 1994](http://dx.doi.org/10.1016/0304-3975%2894%2990244-5)) by representing each cell in a two-dimensional cellular automata as an O(log n)-bit binary string.
Tsuyoshi Ito
<cc.complexity-theory><circuit-complexity><permutations>
Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation
QiCheng
# Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation

(Asked by: username_0 on 2011-10-20)

What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit
with $n$ input bits and $n$ output bits computes a permutation
of $\{0,1\}^n$? in the other words, whether every bit strings in
$\{0,1\}^n$ is an output of the circuit for some input?
It looks like a problem which has been studied,
but I cannot find any references.

**Tags:** cc.complexity-theory, circuit-complexity, permutations

> **Comments:**
> **username_1**: The obvious bound is $\mathsf{coNP}$ which also works for $\mathsf{P}$ (check if the function is injective).  
> **username_2**: What do you mean by “an NC0 circuit”?  The usual phrase is “NC0 family of circuits,” which is (perhaps unfortunately) often abbreviated to “NC0 circuit,” but I do not think that you mean an NC0 family of circuits in your question.  
> **username_0**: By an $NC^0$ circuit, I mean that every output bit of the circuit depends only on constant number of input bits.  
> **username_1**: Every output in *every* circuit depends only on constant number of input bits. Circuits classes like $\mathsf{NC^0}$ only make sense when we consider circuits families. Do you mean that there is a fixed value $d$ and we only consider circuits of that fixed depth $d$?  
> **username_0**: Yes I am asking about a family. To make things more clear, you can change $NC^0$ to $NC_5^0$ where every output bit depends only on $5$ input bits in the family.  
> **username_2**: This does not answer your question, but if the problem is generalized so that each output bit is allowed to depend on O(log n) input bits, then I think that the problem is coNP-complete under Turing reducibility.  This follows from the coNP-completeness of the finite reversibility of two-dimensional cellular automata ([Durand 1994](http://dx.doi.org/10.1016/0304-3975%2894%2990244-5)) by representing each cell in a two-dimensional cellular automata as an O(log n)-bit binary string.  

---

## 1 answers

### Answer by username_2 on 2011-10-22. Score: 30 | Accepted answer

### Hardness

Following your comment on the question, we will call a circuit where each output bit depends on at most *k* input bits a “NC0*k* circuit.” Using this term, your problem is coNP-complete in case of NC05 circuits. That is, the following problem is coNP-complete.

*Instance*: A Boolean circuit *C* with *n* input bits and *n* output bits where each output bit depends on at most five input bits.  
*Question*: Is the mapping from {0,1}*n* to itself computed by *C* bijective?

As username_1 commented, it is clearly in coNP, even without the bound on the number of input bits on which each output bit depends. To prove the coNP-hardness, we will reduce 3SAT to the complement of the current problem. The key idea of the reduction is the same as the one used in the paper [Dur94] by Durand, which I mentioned in a comment on the question, but the whole reduction is much simpler in our case.

Given a 3CNF formula *φ* with *n* variables and *m* clauses, we construct a Boolean circuit *C* with (*n*+*m*) input bits and (*n*+*m*) output bits as follows. We label the input bits as *x*1, …, *x**n*, *y*1, …, *y**m*, and the output bits as *x*′1, …, *x*′*n*, *z*1, …, *z**m*. We consider that the input bits *x*1, …, *x**n* specify a truth assignment to the *n* variables in *φ*.

* *x*′*i* = *x**i* for 1≤*i*≤*n*. That is, the first *n* bits of input are always copied to the first *n* bits of output.
* For 1≤*i*≤*m*, if the *i*th clause of *φ* is satisfied, then *z**i* = *y**i* ⊕ *y**i*+1, where the subscript is interpreted modulo *m*. Otherwise, *z**i* = *y**i*.

Note that each output bit depends on at most five input bits. I omit the proof of the correctness of the reduction, but the key idea (which I borrowed from [Dur94]) is that if *φ* is satisfiable and input bits *x*1, …, *x**n* are set to a satisfying assignment of *φ*, then the *m* output bits *z*1, …, *z**m* are constrained to have the even parity, and therefore the circuit cannot be a permutation. On the other hand, if input bits *x*1, …, *x**n* are set to a non-satisfying assignment of *φ*, then output bits *z*1, …, *z**m* can be set to anything; because of this, if *φ* is unsatisfiable, then the circuit is a permutation.

### Tractability

On the tractable side, your problem is in P in case of NC02 circuits. This is shown as follows. In general, each output bit in a Boolean circuit for a permutation is *balanced*; i.e., exactly half of the input strings set the output bit to 1. However, every balanced Boolean function from {0,1}2 to {0,1} is *affine*; i.e., a copy of a single input bit, the XOR of the two input bits, or the negation of them. Therefore, we can first check that each output bit is balanced, and then check the bijectivity by the Gaussian elimination.

I do not know the complexity in case of NC03 circuits or in case of NC04 circuits.

### References

[Dur94] Bruno Durand. Inversion of 2D cellular automata: some complexity results. *Theoretical Computer Science*, 134(2):387–401, Nov. 1994. DOI: [10.1016/0304-3975(94)90244-5](http://dx.doi.org/10.1016/0304-3975%2894%2990244-5).

> **Comments:**
> **username_2**: I posted a [follow-up question](http://cstheory.stackexchange.com/questions/12351/deciding-whether-an-nc0-3-circuit-computes-a-permutation-or-not) about the case of NC^0_3 circuits.  

---

