Circuit Complexity Boolean function f:{0,1}"10,1) ●DAG(directed acyclic graph) Boolean Λ ●Nodes: circuit ● inputs:1...n ●gates:∧V7 ●Complexity:#gates X1 X2 X3
Circuit Complexity ∧ ¬ x1 x2 x3 ∨ ∧ ∨ f : {0, 1} Boolean function n {0, 1} Boolean circuit • DAG (directed acyclic graph) • Nodes: • inputs: • gates: ∧ ∨ ¬ • Complexity: #gates x1 ...xn
Theorem (Shannon 1949) There is a boolean function f:{0,1n→{0,1}which cannot be computed by any circuit with gates. Claude Shannon
Claude 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
#off:{0,1}”→{0,1} 0,12=2 of circuits with t gates: <2(2n+t+1)2t A,v gates X1,,xn,7x1,.,7xn,0,1 De Morgan's law: xi,7xi,0,1 (AVB)=A∧B other (1-1)gates (A∧B)=AVB
∧,∨ # of circuits with t gates: ∧,∨ gates x1,...,xn,¬x1,...,¬xn,0,1 De Morgan’s law: ¬(A ⇤B) = ¬A ⇥¬B ¬(A ⇥B) = ¬A ⇤¬B 2 (2n + t +1) t 2t other (t-1) gates xi ,¬xi ,0,1 < # of f : {0, 1}n {0, 1} {0, 1}2n = 22n
Theorem(Shannon 1949) Almost all Thereisaboolean function f:(0,1)(0,1} which cannot be computed by any circuit with 薪gates.. one circuit computes one function #fcomputable by t gates s #circuits with t gates s 2(2n+t+1)2t 22”=#f t=2713n
There 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
Double Counting "Count the same thing twice. The result will be the same." 小小小小 小 sum by row A A=B sum by column B
Double Counting sum by row A sum by column B A=B “Count the same thing twice. The result will be the same