Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
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. –  Theo Johnson-Freyd Mar 10 '11 at 1:47
1  
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. –  Yemon Choi Mar 10 '11 at 4:56
    
What is the relation of $N$ to $n$, and what exactly is a “permutation of $N$ bits”? –  Emil Jeřábek Mar 10 '11 at 14:04
    
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)$. –  Vivek Shende Mar 10 '11 at 15:47
    
That's interesting. But what would then be the question? One cannot compute anything but permutations with reversible circuits. –  Emil Jeřábek Mar 10 '11 at 16:50
add comment

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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