Circuit Complexity Boolean function f:{0,1){0,1) ·DAG(directed acyclic graph) Boolean ·Nodes: circuit ●inputs:r1..xn ●gates:∧V7 ·Complexity:#8ates X 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