<p>I will point out a simple connection to nondeterministic circuits, and comment briefly on cryptographic hardness.</p>

<p>For $S \subseteq \{0, 1\}^n$, define the <em>image complexity,</em> 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$).</p>

<p>Also define the <em>nondeterministic circuit complexity</em> 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)$.</p>

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

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

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

CC BY-SA 3.0
2013-10-16T15:45:23.253Z
2013-10-21T18:19:54.103Z
2013-10-21T18:19:54.103Z
Andy Drucker
<p>You should have a look at <a href="http://www.cs.sfu.ca/~kabanets/Research/circuit.html" rel="nofollow">this paper</a> by Kabanets and Cai. I will quote the abstract of the paper:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

CC BY-SA 3.0
2013-10-16T11:57:15.730Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-16T12:23:19.177Z
I've just updated my answer to address your comment.
Dai Le
CC BY-SA 3.0
2013-10-16T13:05:31.080Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-16T14:07:07.070Z
I've added more explanation.
Dai Le
CC BY-SA 3.0
2013-10-16T22:41:41.653Z
I am not sure this solves the question. A circuit $C'$ as described in the question would take $n$ inputs and its range will be $L$. And you have shown that such a circuit will have size at most an additive $n$ larger than the circuit complexity of $f$. But now you need to also show how to construct a circuit computing $f$ from $C'$, and I don't see how to do that directly. Andy's answers shows a way around this problem, though.
Sasho Nikolov
CC BY-SA 3.0
2013-10-16T23:45:48.547Z
@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
CC BY-SA 3.0
2013-10-16T11:55:18.867Z
2013-10-16T23:48:45.477Z
2013-10-16T23:48:45.477Z
Dai Le
<p>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.</p>

<p>However, I want to represent $L$ with a Boolean circuit $C'$ with $n$ <em>outputs</em> 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$.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>(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.)</p>

CC BY-SA 3.0
2013-10-16T12:03:57.137Z
This paper does not answer your question but studies the kind of circuits you are looking for http://eccc.hpi-web.de/report/2012/079/
Marcos Villagra
CC BY-SA 3.0
2013-10-16T15:11:03.557Z
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
CC BY-SA 3.0
2013-10-16T17:42:05.743Z
How is $L$ given? By the circuit $C$?
usul
<fl.formal-languages><circuit-complexity>
Smallest Boolean circuit to generate a language
Antoine Amarilli 'a3nm'
# Smallest Boolean circuit to generate a language

(Asked by: username_0 on 2013-10-16)

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

**Tags:** fl.formal-languages, circuit-complexity

> **Comments:**
> **username_1**: This paper does not answer your question but studies the kind of circuits you are looking for http://eccc.hpi-web.de/report/2012/079/  
> **username_2**: 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...  
> **username_3**: How is $L$ given? By the circuit $C$?  

---

## 2 answers

### Answer by username_4 on 2013-10-16. Score: 11 | Accepted answer

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 username_5 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 by username_5 on 2013-10-16. Score: 5

You should have a look at [this paper](http://www.cs.sfu.ca/~kabanets/Research/circuit.html) 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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: I've just updated my answer to address your comment.  
> **username_0**: 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.  
> **username_5**: I've added more explanation.  
> **username_6**: I am not sure this solves the question. A circuit $C'$ as described in the question would take $n$ inputs and its range will be $L$. And you have shown that such a circuit will have size at most an additive $n$ larger than the circuit complexity of $f$. But now you need to also show how to construct a circuit computing $f$ from $C'$, and I don't see how to do that directly. Andy's answers shows a way around this problem, though.  
> **username_5**: @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.  

---

