2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
15
  • $\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$
    – user54001
    Commented Apr 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$ Commented Apr 26, 2017 at 17:49
  • $\begingroup$ Maybe you could give me some intuition why it holds ? $\endgroup$
    – user54001
    Commented Apr 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$ Commented Apr 26, 2017 at 18:10
  • $\begingroup$ So you represent function as CNF formula. I know that for CNF formula it is easy to draw a tree. But why using CNF forces $O(2^nn)$ gates I don't understand. $\endgroup$
    – user54001
    Commented Apr 26, 2017 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.