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.)

• This paper does not answer your question but studies the kind of circuits you are looking for eccc.hpi-web.de/report/2012/079 – Marcos Villagra Oct 16 '13 at 12:03
• from your comments below it seems you more want to consider a family of circuits where $L$ is not finite. guess your function must also be surjective and cant be bijective in general... – vzn Oct 16 '13 at 15:11
• How is $L$ given? By the circuit $C$? – usul Oct 16 '13 at 17:42

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 > 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.

You should have a look at this paper by Kabanets and Cai. I will quote the abstract of the paper:

We study the complexity of the circuit minimization problem: given the truth table of a Boolean function $f$ and a parameter $s$, decide whether $f$ can be realized by a Boolean circuit of size at most $s$. We argue why this problem is unlikely to be in $\mathsf{P}$ (or even in $\mathsf{P}/\mathsf{poly}$) by giving a number of surprising consequences of such an assumption. We also argue that proving this problem to be $\mathsf{NP}$-complete (if it is indeed true) would imply proving strong circuit lower bounds for the class $\mathsf{E}$, which appears beyond the currently known techniques.

Although the circuit $C'$ you mentioned computes a function $F:\{0,1\}^m \rightarrow L$, we can think of it as a sequence of circuits $C'_1,C'_2,\ldots,C'_n$, where $C'_i$ computes the $i^{\rm th}$ output bit of $F$. Since each $C'_i$ computes a boolean function $\{0,1\}^m\rightarrow \{0,1\}$, minimizing the circuits $C'_i$ seems hard according to the above result.

• Thanks! However, I do not wish to realize a fixed function $f$ with my circuit $C'$: I am OK with realizing any function $f$ as long as its image is $L$. So I am not trying to solve their problem of realizing a certain function $f$, so I do not think that this hardness result would still apply. – a3nm Oct 16 '13 at 11:57
• I've just updated my answer to address your comment. – Dai Le Oct 16 '13 at 12:23
• I still disagree. Each $C_i'$ computes a Boolean function as you say, but there are still multiple possible choices for each $C_i'$, even assuming that the other ones are fixed. For instance if $L$ is $\{000, 001, 010, 011\}$, if $C_2'$ is fixed, I still have multiple choices for $C_3'$. I am interested in the hardness of finding a minimal circuit achieving some consistent choices of such Boolean functions, so I do not see a reduction of their problem to mine. – a3nm Oct 16 '13 at 13:05
• I've added more explanation. – Dai Le Oct 16 '13 at 14:07
• @SashoNikolov You're right that $C'$ doesn't have to compute the $F$ I mentioned. It can computes any $F$ whose range is $L$. So we don't know how to contruct $C$ that computes $f$ from $C'$. I will remove that misleading construction. – Dai Le Oct 16 '13 at 23:45