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.
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
cc.complexity theory;open problem;permutations;circuit families