Boolean function
There are two major notions of circuit complexity The circuit-size complexity of a Boolean function formula_6 is the minimal size of any circuit computing formula_6. The circuit-depth complexity of a Boolean function formula_6 is the minimal depth of any circuit computing formula_6.