1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$) $\endgroup$
    – D.W.
    Apr 17 at 8:04
  • $\begingroup$ Yes! I added this condition to impose that $m$ cannot be unnecessarily large. In particular, this condition prevents to always take $m=n$. $\endgroup$ Apr 17 at 8:32

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The proof is convincing! Going outside the scope of the question, do you think that using quantum circuits (under some suitably weaker conditions) could change the result? If I correctly understand, some hash functions could be effectively inverted by quantum calculation but not all of them, so your informal proof should hold even for quantum circuits. Is this correct? $\endgroup$ Apr 17 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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