Smallest Boolean circuit to generate a language

Question

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

Answer 1

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.

Answer 2

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.