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

方針. 大きさ $2$ 以下の回路で計算できる関数を、本質的に依存する変数の個数で分けて数える。$\{0,1\}$ を ${\mathbb{F}}_2$ と同一視し、関数の区別には代数標準形（ANF）を使う。

(1) 高々 $2$ 変数にしか依存しない関数.
入力ノード $x_i$ を出力とすれば $x_i$ が得られる。ゲートを $1$ 個使えば、任意の $i,j$ と任意の $2$ 入力関数 $g$ について $g(x_i,x_j)$ が得られる。これで定数・$x_i$・$\neg x_i$ もすべて得られる。逆に、ゲート $1$ 個の回路が計算する関数は高々 $2$ 変数にしか依存しない。したがって、ちょうど $2$ 変数に本質的に依存する $2$ 変数関数 $g$（以下、非退化という）の個数を求めればよい。それは $16-2-4=10$ 個で、内訳は
- AND 型 $8$ 個：$(x\oplus b)(y\oplus d)\oplus e$
- XOR 型 $2$ 個：$x\oplus y\oplus e$

である。よってこの種類の関数は
$$2+3\cdot 2+3\cdot 10=38\text{ 個}$$
あり、いずれも $C(f)\le 1$ である。

(2) $3$ 変数すべてに依存し、ゲート $2$ 個で計算できる関数.
出力が $2$ 個目のゲート $g_2$ である場合だけを考えればよい。$g_2$ の入力の組み合わせで分けると次のとおり。
- $g_2$ が $g_1$ を使わない場合、または入力が $(g_1,g_1)$ の場合：高々 $2$ 変数に依存する。
- 入力が $g_1=g(x_i,x_j)$ と $x_l$（$l\in \{i,j\}$）の場合：高々 $2$ 変数に依存する。
- 入力が $g_1$ と $x_k$（$\{i,j,k\}=\{1,2,3\}$）の場合：$f=h(g(x_i,x_j),x_k)$ となる。

この形の関数で $3$ 変数すべてに依存するものの集合を $S_k$ とする。$3$ 変数すべてに依存するには $g$ が非退化であることが必要である。$f{|}_{x_k=0}=u_0(g)$、$f{|}_{x_k=1}=u_1(g)$ と書くと、$u_0,u_1\in \{0,1,\mathrm{id},\neg \}$ であり、条件は $u_0\ne u_1$ かつ「$u_0,u_1$ がともに定数ではない」ことである。制限の組 $(A,B)=(f{|}_{x_k=0},f{|}_{x_k=1})$ は次の $2$ 種類になる。
- 型 I：$B=\neg A$（$A$ は非退化）。$f=A(x_i,x_j)\oplus x_k$ で、$10$ 個。
- 型 II：一方が定数で他方が非退化。$f=c\oplus (x_k\oplus a)D(x_i,x_j)$（$D$ は非退化）で、$2\cdot 2\cdot 10=40$ 個。

よって $|S_k|=50$ である。次に、$S_1,S_2,S_3$ の重なりを ANF の形で調べる。
- 型 I で $A$ が XOR 型：$x_1\oplus x_2\oplus x_3\oplus e$ の $2$ 個。これはすべての $S_k$ に属する。
- 型 I で $A$ が AND 型：ANF の $2$ 次の部分が $x_i{x}_j$ だけ、$3$ 次の項はない。ほかの形と一致しないので、$S_k$ 固有の関数が $8$ 個ある。
- 型 II で $D$ が XOR 型：$2$ 次の部分が $x_k{x}_i+x_k{x}_j$ で、$k$ が決まる。$S_k$ 固有の関数が $8$ 個ある。
- 型 II で $D=(x_i\oplus b)(x_j\oplus d)\oplus e$、$e=0$：$c\oplus$（$3$ つのリテラルの積）となる。これは $k$ について対称なので、すべての $S_k$ に属し、$2\cdot 8=16$ 個ある。
- 型 II で $D=(x_i\oplus b)(x_j\oplus d)\oplus e$、$e=1$：$c\oplus {\ell }_k\wedge (m_i\vee m_j)$（$\ell ,m$ はリテラル）となり、重みは $3$ または $5$ である。たとえば $x_3\wedge (x_1\vee x_2)$ を考える。$x_1$ について制限すると $x_2{x}_3$ と $x_3$ になり、どちらも定数でなく互いの否定でもない。したがって $S_1$ に属さない（$S_2$ についても同様）。よって $S_k$ 固有の関数が $2^4=16$ 個ある。

各 $S_k$ の内訳は $8+2+8+16+16=50$ で、上の計算と合う。和集合の大きさは
$$|S_1\cup S_2\cup S_3|=3(8+8+16)+(2+16)=96+18=114.$$

(3) 合計. $(1)$ と $(2)$ を合わせて
$$38+114=152.$$

$C(f)\le 2$ となる $f$ を、ゲート数ごとに数える。

ゲート数 0〜1。 出力が入力ノードなら $x_1,x_2,x_3$ の $3$ 個。ゲートが $1$ 個のとき、$g(x_i,x_j)$（$i=j$ も可）で表せるのは、高々 $2$ 変数に依存する関数すべてである。その個数は次のとおり。
- 定数: $2$ 個
- ちょうど $1$ 変数に依存する関数 $x_i,\neg x_i$: $6$ 個
- ちょうど $2$ 変数に依存する関数: 変数の組ごとに $16-2-4=10$ 個で、組は $3$ 通りなので $30$ 個

合計 $38$ 個。これは $C\le 1$ の関数の個数である。

ゲート数 2。 出力は第 2 ゲート $h$ の出力としてよい。$h$ の入力は入力ノードか第 1 ゲート $g(x_a,x_b)$ である。$h$ の入力が両方入力ノードなら $C\le 1$ の関数になる。$h(g,g)$ も $1$ 変数の関数 $g$ になるので同様である。よって新しい関数は $F=h(g(x_a,x_b),x_c)$ の形に限る。$c\in \{a,b\}$ なら高々 $2$ 変数に依存するので既出である。したがって $\{a,b,c\}=\{1,2,3\}$ とし、$3$ 変数すべてに依存する関数を数える。

このとき $g$ は $a,b$ の両方に依存し、$h$ も両引数に依存する。両方に依存する関数は各 $10$ 個（AND 型 $8$ 個と XOR 型 $2$ 個）である。$g$ と $\neg g$ は $h$ を取り替えれば同じ $F$ を与えるので、$g$ は $5$ 類（AND 型 $4$ 類と XOR 型 $1$ 類）に分ける。$g$ の類を決めると $h$ の $10$ 通りは異なる $F$ を与える。よって各 $c$ について $5\times 10=50$ 個で、その型は次のとおり。
- パリティ $x_1\oplus x_2\oplus x_3$ とその否定: $2$ 個
- $\ell (x_c)\wedge (x_a\oplus x_b{)}^{\pm }$ とその否定の形（$\ell$ はリテラル）: $8$ 個
- $(x_a^p{x}_b^q)\oplus x_c$ とその否定の形: $8$ 個
- 3 リテラルの積 $x_a^p{x}_b^q{x}_c^r$ とその否定: $16$ 個
- $\ell (x_c)\wedge (x_a^p\vee x_b^q)$ とその否定の形: $16$ 個

$c$ をまたぐ重複。 パリティ($2$ 個)と 3 リテラルの積およびその否定($16$ 個)は、どの $c$ でも現れる。残りの型は $c$ ごとに別の関数である。たとえば $c^{\prime }=a$ で $a=0,1$ に制限した関数が、定数または互いに補関係にある関数の組にならないことから確かめられる。したがって次のようになる。
- $c$ に依らない共通の関数: $2+16=18$ 個
- $c$ ごとに固有の関数: $8+8+16=32$ 個ずつ、$3$ 通りで $96$ 個

$3$ 変数すべてに依存する新しい関数は $18+96=114$ 個である。

合計。 $38+114=152$。