計算理論・ラムダ計算の問題

$f$ が本質的に依存する変数の個数で分けて数える。

(1) 本質的に依存する変数が 2 個以下の関数. これらはすべて大きさ $1$ 以下で計算できる。実際、ゲートとして定数関数や $\neg x$ も使えるので、$x_i,x_j$ に適当な 2 入力ゲートを 1 つ当てればよい。個数は、2 変数の関数 16 個のうち、定数 2 個、1 変数に本質的に依存するもの $x,\neg x,y,\neg y$ の 4 個を除いた $16-2-4=10$ 個が 2 変数に本質的に依存することから
$$2+3\cdot 2+\left(\genfrac{}{}{0ex}{}{3}{2}\right)\cdot 10=2+6+30=38$$
個。

(2) 3 変数すべてに本質的に依存する関数. ゲート 1 個では入力が 2 つなので不可能で、ちょうど 2 個必要。出力ゲート $G_2$ は 3 変数すべてに依存しなければならないので、$G_2$ の入力は 1 つ目のゲート $G_1$ と入力変数 $x_c$ であり、$G_1$ の入力は残りの 2 変数 $x_a,x_b$（$\{a,b,c\}=\{1,2,3\}$）である。よって
$$f=g(h(x_a,x_b),x_c)$$
で、$h,g$ はともに 2 引数に本質的に依存する 2 入力関数（10 個のうちのどれか）である。この 10 個は、AND 型 8 個 $(y\oplus \alpha )\wedge (z\oplus \beta )\oplus \gamma$ と XOR 型 2 個 $y\oplus z\oplus \gamma$ からなり、補関数をとる操作で閉じている。以下、$\ell$ はリテラル（変数またはその否定）を表す。

$g$ が XOR 型のとき: $f=h(x_a,x_b)\oplus x_c\oplus \gamma$ で、$\gamma$ は $h$ を補関数に取り替えれば吸収できるので $f=h\oplus x_c$。
- $h$ が XOR 型: $f=x_1\oplus x_2\oplus x_3\oplus \gamma$ の $2$ 個（$c$ によらない）
- $h$ が AND 型（8 個）: $f=({\ell }_a\wedge {\ell }_b)\oplus {\gamma }^{\prime }\oplus x_c$。代数標準形（ANF）の 2 次の項がちょうど $x_a{x}_b$ なので $c$ が決まり、$3\cdot 8=24$ 個はすべて異なる

計 $26$ 個。これらの次数（ANF の次数）は $1$ または $2$ で、2 次の項は高々 1 つ。

$g$ が AND 型のとき: $\alpha$ は $h$ の補関数で吸収できるので $f=(h(x_a,x_b)\wedge {\ell }_c)\oplus \gamma$。
- $h={\ell }_a\wedge {\ell }_b$: $f=({\ell }_1\wedge {\ell }_2\wedge {\ell }_3)\oplus \gamma$。リテラルの符号 $2^3$ 通りと $\gamma$ で $16$ 個（$c$ によらない）
- $h=\neg ({\ell }_a\wedge {\ell }_b)={\ell }_a^{\prime }\vee {\ell }_b^{\prime }$: $f=(({\ell }_a\vee {\ell }_b)\wedge {\ell }_c)\oplus \gamma$。${\ell }_c$ を偽にする $x_c$ の値でだけ $f$ が定数になる（${\ell }_a$ を偽にしても ${\ell }_b\wedge {\ell }_c$ が残る）ので $c$ が $f$ から決まり、さらに残りの部分から符号と $\gamma$ も決まる。$3\cdot 2^3\cdot 2=48$ 個
- $h=x_a\oplus x_b\oplus \delta$: $f=((x_a\oplus x_b\oplus \delta )\wedge {\ell }_c)\oplus \gamma$。ANF の 2 次の項は $x_a{x}_c+x_b{x}_c$ でちょうど 2 つあり、共通の変数として $c$ が決まる。$3\cdot 2\cdot 2\cdot 2=24$ 個

最初の 2 種類は ANF に $x_1{x}_2{x}_3$ を含む（次数 $3$）が、真になる点の個数が $1$ または $7$ 個と $3$ または $5$ 個で異なる。3 種類目は次数 $2$ で 2 次の項が 2 つ。よって互いに重ならず、計 $16+48+24=88$ 個。さらに XOR 型の $26$ 個とも、次数と 2 次の項の個数で区別できるので重ならない。

どれも 3 変数すべてに本質的に依存しているので (1) とも重ならない。したがって (2) の個数は $26+88=114$。

合計.
$$38+114=152.$$

大きさ 2 以下の回路で計算できる関数を、本質的に依存する変数の個数で分けて数える。

(1) 大きさ 1 以下（ゲート 0 個または 1 個）。入力変数そのもの、または 1 個のゲート $g(a,b)$ の出力。定数 $0,1$ が 2 個。1 変数関数（$x_i,\neg x_i$）が $3\times 2=6$ 個。ちょうど 2 つの変数 $x_a,x_b$ に本質的に依存する 2 変数関数は、16 個の 2 入力関数のうち定数 2 個と片方だけの関数 4 個を除いた 10 個で、変数の組が 3 通りあるので 30 個。合計 $2+6+30=38$ 個。3 変数以下に依存するどんな 2 変数以下の関数も 1 ゲートで作れるので、これで 2 変数以下の関数はすべて尽くされる。

(2) 大きさ 2 で、3 つの変数すべてに本質的に依存するもの。ゲート $G=g(x_a,x_b)$ の出力と別のゲート $h(u,v)$ を考える。$u,v\in \{x_1,x_2,x_3,G\}$。3 変数すべてに依存するには $G$ が $x_a,x_b$ の両方に本質的に依存し、$h(G,x_c)$（$c$ は残りの変数）の形でなければならない。$F=h(G,x_c)$ は、$x_c=0$ のときの関数 $F_0$ と $x_c=1$ のときの関数 $F_1$ が $\{0,1,G,\neg G\}$ の元で、$F_0\ne F_1$ かつ両方定数ではない場合。$G$ は $\{G,\neg G\}$ で分類して 5 類（4 つの符号違いの AND/OR 型と XOR 型）。

AND/OR 型（$G=l_a\wedge l_b$、$l$ はリテラル）の 4 類:
- リテラル 3 つの AND: 8 個、リテラル 3 つの OR: 8 個
- $l_c\wedge (l_a\vee l_b)$ 型: 各 $c$ で $2\times 4=8$ 個、計 24 個
- $l_c\vee (l_a\wedge l_b)$ 型: 同様に 24 個
- $(l_a\wedge l_b)\oplus x_c$ またはその否定: 各 $c$ で 8 個、計 24 個（ANF の 2 次項が異なるので重ならない）

XOR 型:
- $l_c\wedge (x_a\oplus x_b)$ または $l_c\wedge \neg (x_a\oplus x_b)$ 型: 各 $c$ で 4 個、計 12 個
- $l_c\vee (x_a\oplus x_b)$ または $l_c\vee \neg (x_a\oplus x_b)$ 型: 12 個
- パリティ $x_1\oplus x_2\oplus x_3$ とその否定: 2 個（$c$ の選び方によらず同じ）

これらは互いに異なる（形が異なる、または非対称な形で $c$ が一意に決まる）ので、$8+8+24+24+24+24+2=114$ 個。

(3) 合計 $38+114=152$ 個。

検算: (1) は 2 変数以下の関数の個数 $2+6+30=38$ を、$\left(\genfrac{}{}{0ex}{}{3}{2}\right)\times 10$ から数え直して一致。(2) は 3 変数に依存する関数が 114 個で、3 変数関数全体 256 個に収まり、パリティ（次数 1）、2 次の ANF をもつ型、AND/OR 型を ANF の形で区別できることを確認した。