Boolean回路
Boolean Circuits
$ n-input, single outputのBoolean回路とは$ n個の出発点と一つの終着点を持ち以下を満たす有向非巡回グラフ$ Cである $ \land, $ \lorのラベルを持つ頂点の入力は2つ、$ \lnotのラベルを持つ頂点の入力は1つ
出発点でない頂点はgateと呼ばれ$ \land, $ \lor, $ \lnotのラベルをもつ
$ |C|は$ Cの頂点の数を表す
CNFなどの論理式は各頂点の出力を1つに限ったBoolean回路である 深さ depthとは回路の最長の経路の長さを表す
Boolean回路の完全性
hard-functionの存在
任意の$ n > 1についてサイズ$ \frac{2^n}{10n}の回路で表現できない関数$ f : \mathbf{2}^n \to \mathbf{2}が存在する
$ \frac{2^n}{10n}でなくても$ 9 f(n)\log f(n) < 2^nを満たす関数$ fであればなんでもいい
Proof.
関数$ \mathbf{2}^n \to \mathbf{2}の数は$ 2^{2^n}個
サイズ$ sの回路$ C, $ |C| = sは$ \|C\| = 9s\log sの情報量で表現できる（?）。サイズ$ sの回路の数は$ 2^{9s\log s}個以下。 $ s = \frac{2^n}{10n}のときサイズ$ sの回路の個数は$ 2^{9s\log s} \le 2^{2^{n} \frac{9n}{10n}} < 2^{2^n}