We know that a permutation of N bits {0, 1}^N --> {0,1}^N can be computed by circuits of size O(n 2^n). But are there circuits that can be computed only by size O((n^2)(2^n) and not O(n 2^n)

Question

We know that a permutation of N bits {0, 1}^N --> {0,1}^N can be computed by circuits of size O(n 2^n). But are there circuits that can be computed only by size O((n^2)(2^n) and not O(n 2^n)

Answer 1

I have a hard time understanding the original question, but I'll turn my comment in an answer in the hope that it will reduce confusion.

Any function $f\colon\{0,1\}^n\to\{0,1\}^n$ can be computed by a circuit of size at most $(1+o(1))2^n$. This follows from Lupanov’s theorem that any function $g\colon\{0,1\}^n\to\{0,1\}$ can be computed by a circuit of size $(1+o(1))2^n/n$. (An accessible presentation of the result can be found in these lecture notes.)

In general, this bound is optimal up to a multiplicative factor, even for permutations $f\colon\{0,1\}^n\to\{0,1\}^n$. This follows by a counting argument: a circuit of size $s$ can be described using $O(s\log s)$ bits, hence there are at most $2^{O(s\log s)}$ such circuits. On the other hand, there are $2^n!$ permutations $f$, hence there has to be an $f$ which requires circuit size $s=\Omega(\log(2^n!)/\log\log(2^n!))=\Omega(2^n)$ (using Stirling’s approximation $\log(2^n!)=\Theta(2^nn)$).

Answer 2

Any function $f:V^n \rightarrow V^n$ can be computed with $O(n 2^n)$ gates as follows. For each input $\langle v_1, \dots, v_n \rangle$, compute $t_v = x_1^{v_1} \wedge \dots \wedge x_n^{v_n}$ (where exponentiation is defined as: $x^0$ means $\neg x$, $x_1$ mean $x$). This requires $2^n (n-1)$ gates.

Then form each output wire as $o_i$ as the disjunction, over all $v$ with $f(v)[i] = 1$, of $t_v$. For each output wire $i$, this requires at most $2^n$ gates. Hence the output wires, in total, require at most $n 2^n$ gates.

The total number of gates is thereby bounded by $O(n 2^n)$.

This does not require that $f$ is a permutation.