より詳しい解説：https://hos-lyric.hatenablog.com/entry/2021/01/14/201304

\(F(x, \ldots, x)\) によって \(x\) の否定 \(\overline{x}\) が求められます．

\(M = 1\) のときはある変数そのままかある変数の否定かしか作れません．

\(L < \frac{M+1}{2}\) とします．\(F(x, \ldots, x, x', \ldots, x')\) (約半分ずつ) の形で \(x \operatorname{NOR} x'\) を求められます．特に \((y_0 \operatorname{NOR} \overline{y_0}) = 0\) や \(\overline{0} = 1\) が手に入ります．任意の論理回路は NOR によって作れるので，\(G\) を実現できます．\(O(2^N \mathrm{poly}(N))\) 個の命令を使用します．

\(L > \frac{M+1}{2}\) のときも NAND が求められて同様に解けます．

\(L = \frac{M+1}{2}\) とします．このとき常に \(F(\overline{x_0}, \ldots, \overline{x_{M-1}}) = \overline{F(x_0, \ldots, x_{M-1})}\) が成り立つので，\(G\) が実現可能であるためには \(G(\overline{y_0}, \ldots, \overline{y_{N-1}}) = \overline{G(y_0, \ldots, y_{N-1})}\) が必要です．逆にこの条件を満たすとき，\(y_{N-1} = 0\) なる任意の入力に対して正しければ \(y_{N-1} = 1\) のときも正しいので，\(y_{N-1} = 0\) だと思うことができます．すると，\(F(x, \ldots, x, x', \ldots, x', 0)\) の形で NAND が求められるので，\(G\) を実現できます．