Multiplicative Depth

• 乗法的深さ
  • 関数 $d:V\to \{0,1\}$ : ANDノードなら1, それ以外なら0 を返す.
• 回路のmult-depth は最大の乗法的深さのパスになる.
• 回路の乗法的深さを $l:V\to \mathbb{N}$ で与える

$$l(v)=\underset{n\in c(v)}{\max }l(n)+\{\begin{array}{ll}1& (v.\text{op}=\times )\\ 0& (\text{otherwise})\end{array}$$