n-bit 加減乗除回路が O(log n) 深さで実装できることを知った。
任意の n-bit ブール関数が O(n) 深さで実装できることはすぐに分かる。独立な n-bit ブール関数が全部で 2^(2^n) 通りあるうんぬんかんぬんで、これが下限な気がするが自信がない。
O(log n) 深さの回路では計算不可能なブール関数が存在すると強く予想されているのにも関わらず、明 示的関数に対して、この予想は現在未解決である。
んんんんこの文章の前半は文字通り証明されていないと理解していいの? 何を間違えているんだ。