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.
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ The obvious bound is $\mathsf{coNP}$ which also works for $\mathsf{P}$ (check if the function is injective). $\endgroup$– KavehOct 20, 2011 at 7:18
-
$\begingroup$ 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. $\endgroup$– Tsuyoshi ItoOct 20, 2011 at 14:18
-
1$\begingroup$ By an $NC^0$ circuit, I mean that every output bit of the circuit depends only on constant number of input bits. $\endgroup$– QiChengOct 20, 2011 at 18:32
-
3$\begingroup$ 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. $\endgroup$– QiChengOct 21, 2011 at 16:47
-
1$\begingroup$ 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) by representing each cell in a two-dimensional cellular automata as an O(log n)-bit binary string. $\endgroup$– Tsuyoshi ItoOct 22, 2011 at 22:10
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
Hardness
Following your comment on the question, we will call a circuit where each output bit depends on at most k input bits a “NC0k 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 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.
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 x1, …, xn, y1, …, ym, and the output bits as x′1, …, x′n, z1, …, zm. We consider that the input bits x1, …, xn specify a truth assignment to the n variables in φ.
- x′i = xi 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 ith clause of φ is satisfied, then zi = yi ⊕ yi+1, where the subscript is interpreted modulo m. Otherwise, zi = yi.
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 x1, …, xn are set to a satisfying assignment of φ, then the m output bits z1, …, zm are constrained to have the even parity, and therefore the circuit cannot be a permutation. On the other hand, if input bits x1, …, xn are set to a non-satisfying assignment of φ, then output bits z1, …, zm 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.
answered Oct 22, 2011 at 22:41
-
3$\begingroup$ I posted a follow-up question about the case of NC^0_3 circuits. $\endgroup$ Aug 19, 2012 at 20:44