戸田の定理(計算量)

$\langle u,y\rangle$ の長さは $\lvert u\rvert$ と $\lvert y\rvert$ だけで決まるので、2・3 で $N_1$ に渡す入力の長さは $u$ の長さだけで決まり、証明書の長さ $w_1(\lvert\langle u,y\rangle\rvert)$ も $\lvert u\rvert$ だけで決まる。
1。和：$W:=\max(w_1,w_2)$ とし、長さ $1+W$ の証明書 $z=(b,z')$ を、$b=0$ のとき「$z'$ の先頭 $w_1$ ビットで $R_1$ が成り立ち、残りのビットがすべて $0$」、$b=1$ のとき同様に $R_2$ で受理する。積：$z=(z_1,z_2)$（長さ $w_1+w_2$）を、$R_1(u,z_1)$ かつ $R_2(u,z_2)$ のとき受理する。$1$ を足すには、和の構成で $R_2$ を「$z$ がすべて $0$」に取り替える。
2。証明書 $z=(y,z')$ を、$B(u,y)$ かつ $R_1(\langle u,y\rangle,z')$ のとき受理する。各 $y$ について条件を満たす $z'$ の個数は $N_1(\langle u,y\rangle)$ なので、受理される $z$ の個数は和に等しい。
3。証明書 $z=(z_1,\dots,z_s)$ を、すべての $i$ で $R_1(\langle u,i\rangle,z_i)$ のとき受理する。受理される $z$ の個数は積に等しい。
どの場合も、証明書を切り分けて $R_1,R_2$ を多項式回呼ぶだけなので、時間と証明書の長さは多項式で抑えられる。$\square$

$y\ne y'$ とし、$d:=y+y'\ne0$ とする。$(A,b)\mapsto(Ay+b,\,Ad)$ を考える。$d$ の $0$ でない成分を $i$ とすると、$A$ の第 $i$ 列以外を固定したとき、第 $i$ 列 $\mapsto Ad$ は $\{0,1\}^k$ の全単射（平行移動）なので、$Ad$ は一様に分布する。さらに $A$ を固定すると $b\mapsto Ay+b$ は全単射なので、$(Ay+b,Ad)$ は $\{0,1\}^k\times\{0,1\}^k$ 上に一様に分布する。$(h(y),h(y'))=(Ay+b,\,Ay+b+Ad)$ はこの組の全単射な像なので、やはり一様に分布する。$\square$

$\pi:=2^{-k}$、$\sigma:=\lvert S\rvert$ とおくと、仮定から $\sigma\pi\in[1/4,1/2]$ である。$y\in S$ について、事象 $E_y$ を「$h(y)=0^k$ で、$S$ のほかのどの $y'$ でも $h(y')\ne0^k$」とする。対ごとに独立なので $\Pr[h(y)=0^k]=\pi$、$y'\ne y$ で $\Pr[h(y)=h(y')=0^k]=\pi^2$ であり、
$$ \Pr[E_y]\ge\Pr[h(y)=0^k]-\sum_{y'\in S,\ y'\ne y}\Pr[h(y)=h(y')=0^k]=\pi-(\sigma-1)\pi^2 $$
である。$E_y$（$y\in S$）は互いに排反で、その和事象がちょうど「ただ 1 つ」の事象なので、確率は $\sigma\pi-\sigma(\sigma-1)\pi^2\ge\sigma\pi-(\sigma\pi)^2$ 以上である。$x\mapsto x-x^2$ は $[1/4,1/2]$ で増加するので、これは $1/4-1/16=3/16\ge1/8$ 以上である。$\square$

要点：$\exists y$ を、ハッシュ関数で $y$ を 1 つに絞った個数の偶奇に置き換え、絞り込みを独立に何度も繰り返して「どれかが奇数」を積と $+1$ で表す。$S$ が空なら個数はつねに偶数なので、誤りは片側にしか出ない。

$Q(N)=N^3(3N+4)$ なので、$2^j\mid N$ なら $2^{3j}\mid Q(N)$ である。また
$$ Q(N)+1=3N^4+4N^3+1=(N+1)^2(3N^2-2N+1) $$
である（右辺を展開すると $3N^4-2N^3+N^2+6N^3-4N^2+2N+3N^2-2N+1$ で、左辺に一致する）。$2^j\mid N+1$ なら $2^{2j}\mid(N+1)^2$ なので、$Q(N)\equiv-1\pmod{2^{2j}}$ である。
後半は、$N$ が偶数なら $N\equiv0$、奇数なら $N\equiv-1\pmod{2}$ から始めて、1・2 を $\ell$ 回使うと法が $2^{2^\ell}$ になることによる。$\square$

lem-toda-step1 を $e:=2$ で $L$ に当てて $q,w,R$ を得る。長さ $n$ の $x$ について $\ell:=\lceil\log_2(q(n)+1)\rceil$、$M:=2^{2^\ell}$ とおくと、$2^\ell\ge q(n)+1$ なので $M>2^{q(n)}$ である。
$$ f(x):=\sum_{r\in\{0,1\}^{q(n)}}Q^{(\ell)}\bigl(N_R(\langle x,r\rangle)\bigr) $$
とおく。$Q$ は係数が非負の整数の多項式なので、lem-toda-closure の 1 を定数回使えば、計数関数 $N'$ から $Q(N')$ を計数関数にもつ述語が作れる。1 回で証明書の長さはおよそ $4$ 倍、判定の時間も定数倍と多項式の和で抑えられ、$4^\ell\le4(q(n)+1)^2$ なので、$\ell$ 回合成しても多項式で収まる。$r$ についての和は lem-toda-closure の 2 で作れるので、$f\in\#\mathrm P$ である。
$A(x):=\#\{r\mid N_R(\langle x,r\rangle)\text{ が奇数}\}$ とおく。lem-toda-step2 により $f(x)\equiv-A(x)\pmod M$ であり、$0\le A(x)\le2^{q(n)}< M$ なので、$A(x)$ は $-f(x)$ を $M$ で割った余り（$0$ 以上 $M$ 未満）に等しい。lem-toda-step1 により、$x\in L$ なら $A(x)\ge\frac34\cdot2^{q(n)}$、$x\notin L$ なら $A(x)\le\frac14\cdot2^{q(n)}$ である。そこで $g(x,v)$ を「$A:=(-v)\bmod M$ を計算し、$A>2^{q(n)-1}$ なら $1$」と定める。$M$ の 2 進表示は $2^\ell+1\le2q(n)+3$ 桁なので、$g$ は多項式時間で計算できる。$\mathrm P^{\#\mathrm P}$ の機械は、$f(x)$ を 1 回問い合わせて $g$ を計算すればよい。$\square$

Valiant の定理（AB07 Theorem 9.8, p. 175）により、$\mathrm{perm}$ は $\#\mathrm P$ 完全である。すなわち、すべての $f\in\#\mathrm P$ は、$\mathrm{perm}$ への問い合わせのできる多項式時間の機械で計算できる（AB07 Definition 9.5, p. 174）。thm-toda-main の機械の $f(x)$ への問い合わせをこの計算に置き換えればよい。この記事では Valiant の定理を証明しない。$\square$

$f=N_R\in\#\mathrm P$ の値は、長さ $w(\lvert u\rvert)$ の $z$ を辞書式の順に 1 つずつ作り、$R(u,z)$ を判定して数えれば、多項式の空間で計算できる（$z$ と数える変数と $R$ の判定に使う空間を使い回す）。$\mathrm P^{\#\mathrm P}$ の機械の各問い合わせの長さは多項式なので、問い合わせのたびにこの計算を実行すれば、全体が多項式の空間で模倣できる。$\square$