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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityThe 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.
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$