# Size of circuit generating the solutions of a SAT problem

We have a satisfiable CNF formula $$F$$ which maps $$\{0,1\}^n \to \{0,1\}$$. Let us call $$S\in \{0,1\}^n$$ the set of inputs that satisfy $$F$$, i.e. $$F(s)=1 \, \forall s\in S$$.

There is a circuit $$C$$ with $$n$$ outputs, $$C:\{0,1\}^m \to \{0,1\}^n$$, that generates all the elements of $$S$$, in the following sense:

1. Given any $$i\in \{0,1\}^m$$, then $$C(i)\in S$$;
2. For each $$s\in S$$, there is a $$i$$ such that $$C(i)\in S$$;
3. At least 1/2 of the outputs are distinct.

This is always trivially possible, even if the circuit could be very large, with the trivial method I have in mind.

I am interested in the size of the circuits $$C$$: how does it scale with the size of $$F$$?

I am not interested in the complexity of finding the solutions $$S$$: the process of calculating the solutions (or the circuit) can be as long as needed.

• Does item 3 mean that there are at least $2^{m-1}$ outputs of $C$ that occur for only a single input to $C$? (i.e., occur only once in the truthtable for $C$)
– D.W.
Commented Apr 17 at 8:04
• Yes! I added this condition to impose that $m$ cannot be unnecessarily large. In particular, this condition prevents to always take $m=n$. Commented Apr 17 at 8:32

Here is a plausibility argument that $$C$$ will need to be large in at least some cases.
Let $$H$$ be a cryptographic hash function (model it as a random oracle). Define $$H(x)[i]$$ to be the $$i$$th bit of the output of $$H$$. Define $$F:\{0,1\}^n \to \{0,1\}$$ by
$$F(x) = H(x)[1] \land \cdots \land H(x)[n/2].$$
Then we expect $$F$$ to have about $$2^{n/2}$$ satisfying assignments. Also any circuit $$C$$ will need to have $$m=n/2$$ or $$m=n/2+1$$. However we can expect $$C$$ will need to have exponential size. (If there was a small circuit $$C$$, it would effectively be inverting the hash function $$x \mapsto H(x)[1..n/2]$$; more formally, if we model $$H$$ as a random oracle, then the set $$S$$ of satisfying assignments behaves as a set of random values, where each $$x \in \{0,1\}^n$$ has a $$1/2^{n/2}$$ chance of being included in $$S$$, and building a circuit to output those $$2^{n/2}$$ values requires on average circuit size $$2^{n/2}/n$$ or larger.)
This is not a formal proof, because we have to make very strong assumptions about the cryptographic hash function. But it suggests that in practice there is probably no hope for proving useful scaling facts about $$C$$.