7
$\begingroup$

There is a basic result in circuit complexity that says:

There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.

The argument is a simple counting argument on the number of boolean functions and the number of distinct circuits. See, for example, these lecture notes.

I believe it is unknown whether or not this bound is tight. That is, we don't know if the following statement is true:

Every language can be solved with circuits of size $O(\frac{2^n}{n})$.

If this statement were true, would it have any interesting implications for complexity theory?

$\endgroup$
7
$\begingroup$

This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see below), for a total of $O(2^{2^k}) + O(2^{n-k})$. Choosing $k = \log (n - \log n)$, we obtain the desired bound.

We compute all possible functions on $k$ inputs inductively. Let $Z_k$ be the size of a circuit computing all possible functions on $k$ inputs. There are two functions on zero inputs, so $Z_0 = 2$. Every function $f(x_1,\ldots,x_k)$ on $k$ inputs can be written as $x_k f(x_1,\ldots,x_{k-1},1) + \overline{x_k} f(x_1,\ldots,x_{k-1},0)$, so $Z_k = Z_{k-1} + 2^{2^k} \cdot O(1)$. The solution of this recurrence is $Z_k = O(2^{2^k})$.

In order to compute the decision tree, we use a similar construction: given a tree $T$ for the first $k-1$ variables, we can construct a tree for the first $k$ variables of the form $x_k T + \overline{x_k} T$. The recurrence we get is $W_k = 2W_{k-1} + O(1)$, whose solution is $W_k = O(2^k)$.

$\endgroup$
  • $\begingroup$ I understood the construction of the decision tree and of the circuit computing all possible outputs, but couldn't quite understand how combining them yields a circuit for $f$. Would you mind elaborating on that a little more? $\endgroup$ – Dean Gurvitz Oct 22 '18 at 6:27
  • $\begingroup$ See Theorem 1.5 here: people.csail.mit.edu/rrw/cs294-2018/hardest-fns.pdf. $\endgroup$ – Yuval Filmus Oct 22 '18 at 6:48

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.