Why each function may be computed with circuit with 2^n gates ?
I am trying to understand this thing, but I can't. In particular why function constant $1$ requires $2^n$ gates. For me, it should be simple to return $1$ regardless of input.
1 Answer
$\begingroup$
$\endgroup$
15
The meaning of the statement is that each function can be computed with at most $2^n$ gates; it doesn't anything about the minimal number of gates needed to compute any function.
That said, you can always add dummy gates to increase the number of gates in your circuit without changing the function it computes. For example, you can replace one of the inputs $x_i$ to $x_i \lor x_i$ to increase the number of gates by 1.
answered Apr 25, 2017 at 20:29
-
$\begingroup$ but I don't still understand it. I know that id does mean: with $2^n$ gates we can compute each function (I understand that sometimes this number of gates is overkill). However, can you explain me why function constantly equals to $1$ requires $2^n$ gates? $\endgroup$– user54001Apr 26, 2017 at 16:35
-
$\begingroup$ It doesn't require $2^n$ gates. that's your (wrong) interpretation of the statement. What the statement was intended to mean is that every function on $n$ inputs can be computed by a circuit containing at most $2^n$ gates. $\endgroup$ Apr 26, 2017 at 17:49
-
$\begingroup$ Maybe you could give me some intuition why it holds ? $\endgroup$– user54001Apr 26, 2017 at 18:07
-
$\begingroup$ You can get a circuit of size $O(2^n n)$ computing a given function on $n$ bits using the CNF or DNF form of the function (indeed, this results in a circuit whose underlying graph is a tree, i.e., a formula). It turns out that you can slightly improve this trivial construction – in fact, every $n$-bit function has a circuit of size $O(2^n/n)$. $\endgroup$ Apr 26, 2017 at 18:10
-
$\begingroup$ So you represent function as
CNFformula. I know that forCNFformula it is easy to draw a tree. But why usingCNFforces $O(2^nn)$ gates I don't understand. $\endgroup$– user54001Apr 26, 2017 at 21:26