Theorem(Shannon 1949) Almost all Thereisaboolean function f:(0,1)-(0,1} which cannot be computed by any circuit 2n withgates. one circuit computes one function #fcomputable by t gates s #circuits with t gates s 2(2n+t+1)2t 22”=#f t=2"/3nThere is a boolean function f : {0, 1}n ￾ {0, 1} which cannot be computed by any circuit with 2n 3n gates. Theorem (Shannon 1949) t = 2n/3n ￾ one circuit computes one function #circuits with t gates ≤ Almost all #f computable by t gates ≤ 2 (2n + t +1) t 2t 22n = #f