10
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This paper does not answer your question but studies the kind of circuits you are looking for eccc.hpi-web.de/report/2012/079 $\endgroup$ – Marcos Villagra Oct 16 '13 at 12:03
  • $\begingroup$ 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... $\endgroup$ – vzn Oct 16 '13 at 15:11
  • 1
    $\begingroup$ How is $L$ given? By the circuit $C$? $\endgroup$ – usul Oct 16 '13 at 17:42
11
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – a3nm Oct 16 '13 at 11:57
  • $\begingroup$ I've just updated my answer to address your comment. $\endgroup$ – Dai Le Oct 16 '13 at 12:23
  • 1
    $\begingroup$ 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. $\endgroup$ – a3nm Oct 16 '13 at 13:05
  • 1
    $\begingroup$ I've added more explanation. $\endgroup$ – Dai Le Oct 16 '13 at 14:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Dai Le Oct 16 '13 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.