27
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The obvious bound is $\mathsf{coNP}$ which also works for $\mathsf{P}$ (check if the function is injective). $\endgroup$ – Kaveh Oct 20 '11 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 Ito Oct 20 '11 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$ – QiCheng Oct 20 '11 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$ – QiCheng Oct 21 '11 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 Ito Oct 22 '11 at 22:10
29
$\begingroup$

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 x1, …, xn, z1, …, zm. We consider that the input bits x1, …, xn specify a truth assignment to the n variables in φ.

  • xi = xi for 1≤in. That is, the first n bits of input are always copied to the first n bits of output.
  • For 1≤im, if the ith clause of φ is satisfied, then zi = yiyi+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.

$\endgroup$

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.