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 X3Circuit 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