Theorem(Shannon 1949) There is a boolean function f:{0,1}n→{0,1}which cannot be computed by any circuit with gates. Claude ShannonClaude Shannon Theorem (Shannon 1949) There is a boolean function f : {0, 1}n ￾ {0, 1} which cannot be computed by any circuit with 2n 3n gates