メモ

AND, OR, NOTからなるn入力1出力サイズsの回路の数の上限は, 2^s (2+2n+s)^s2^s (2+2n+s)^{2s}.
素子の数をk, ファンインの数を高々mにして同様の上限を考えると, k^s (2+2n+s)^sk^s (2+2n+s)^{ms}.