2
$\begingroup$

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)

$\endgroup$
5
  • $\begingroup$ Similarly to your other question, I'd like to recommend that you look over this one, correct any punctuation, ... --- and remember that MathOverflow does have very robust LaTeX support, so you can use fancier formatting if you like. And I'd more strongly recommend that you provide a bit more background and motivation, if you can. $\endgroup$ Mar 10, 2011 at 1:47
  • 1
    $\begingroup$ I would second Theo's recommendation, even more strongly. One reason to give extra context is that it gives people an idea of how to pitch an answer, should they wish to give one. $\endgroup$
    – Yemon Choi
    Mar 10, 2011 at 4:56
  • $\begingroup$ What is the relation of $N$ to $n$, and what exactly is a “permutation of $N$ bits”? $\endgroup$ Mar 10, 2011 at 14:04
  • $\begingroup$ If by "permutation" the OP means that the function should be invertible, perhaps he would also like the circuits to consist of only invertible gates. In this case I am not aware of any construction to produce circuits of size smaller than $\Theta(n 2^n)$. $\endgroup$ Mar 10, 2011 at 15:47
  • $\begingroup$ That's interesting. But what would then be the question? One cannot compute anything but permutations with reversible circuits. $\endgroup$ Mar 10, 2011 at 16:50

2 Answers 2

5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0

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.