Smallest Boolean circuit to generate a language Consider a non-empty language $L$ of binary strings of length $n$. I can describe $L$ with a Boolean circuit $C$ with $n$ inputs and one output such that $C(w)$ is true iff $w \in L$: this is well-known.

However, I want to represent $L$ with a Boolean circuit $C'$ with $n$ outputs and a certain number of inputs, say $m$, such that the set of the output values of $C'$ for each of the $2^m$ possible inputs is exactly $L$.


  Given $L$, how can I find such a circuit $C'$ of minimal size, and what is the complexity? Is there any relationship between known bounds about the size of circuits of the first kind ($C$) and circuits of this second kind ($C'$), or the complexity of finding them?


(Observe that there is some sort of duality in the following sense: given $C$, I can easily decide if an input word $w$ is in $L$ by evaluating the circuit, but it is NP-hard in general to find some word in $L$ by finding an assignment such that the output is true. Given $C'$ it is likewise NP-hard to decide if some input word $w$ is in $L$ because I have to see if an assignment yields $w$ as output, but it is easy to find some word in $L$ by evaluating the circuit on any arbitrary input.)
I will point out a simple connection to nondeterministic circuits, and comment briefly on cryptographic hardness.

For $S \subseteq \{0, 1\}^n$, define the image complexity, denoted $imc(S)$, as the minimal number of gates in any (fanin-two, AND/OR/NOT) Boolean circuit $C: \{0, 1\}^m \rightarrow \{0, 1\}^n$ whose image is $S$.  The question asks about the complexity of computing $imc(S)$, given a truth-table representation of $S$ (a string of length $2^n$).

Also define the nondeterministic circuit complexity of $S$, which we'll denote $ncc(S)$, as the smallest nondeterministic circuit $C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$ accepting exactly $S$.  That is, we require of $C$ that $x \in S$ iff $\exists y: C(x, y) = 1$.  This is a standard notion, used to define the non-uniform class $NP/poly$: it is the class of all sets $S = \{S_n\}_{n &gt; 0}$, with $S_n \subseteq \{0, 1\}^n$, such that $ncc(S_n) \leq poly(n)$.

What I wanted to point out is that $imc(S) = ncc(S) \pm O(n)$.  Both directions of this inequality are simple to verify.  

Let $dcc(S)$ denote the deterministic circuit complexity.  Using Razborov-Rudich, the paper that Dai Le mentions shows (roughly speaking here) that under certain cryptographic assumptions, it is computationally hard to distinguish truth-tables of $S$ with $dcc(S)$ small, from truth-tables of truly random $S$ (with $dcc(S)$ near-maximal).  Random $S$ also have $ncc(S)$ nearly-maximal, and we of course have $ncc(f) \leq dcc(f)$. So your problem is hard under the same assumptions.

Which is harder to compute given a truth-table for $S$, $dcc(S)$ or $ncc(S)$?  Is there a reduction either way?  I don't know.