IP=PSPACE(IP equals PSPACE)とは、計算能力に制限のない証明者が確率的な多項式時間の検証者と多項式回の対話をする対話証明で認識できる言語のクラス $\mathrm{IP}$ が、多項式の領域で判定できる言語のクラス $\mathrm{PSPACE}$ に等しいという定理で、Lund・Fortnow・Karloff・Nisan と Shamir による。$\mathrm{IP}\subset\mathrm{PSPACE}$ が成り立つのは、最善の証明者の受理確率が多項式の領域で計算できるからである。逆向きの包含は、論理式を有限体上の多項式に書き直し、多項式の和を 1 変数ずつ乱数の点で確かめる和検査プロトコルによる。これで充足する割り当ての個数を対話証明でき、量化記号の積に次数を下げる線形化をはさむと PSPACE 完全な量化論理式の真偽も対話証明できる。
IP=PSPACE は、計算能力に制限のない証明者が確率的な多項式時間の検証者と対話して命題を納得させる 対話証明 で認識できる言語のクラス $\mathrm{IP}$ が、多項式の領域(メモリ)で判定できる言語のクラス $\mathrm{PSPACE}$ と一致するという定理である。Lund・Fortnow・Karloff・Nisan が充足する割り当ての個数の対話証明を与え(とくに $\mathrm{coNP}\subset\mathrm{IP}$ となる)、続いて Shamir が等号を示した(AB07 Theorem 8.17、p. 157、第 8 章の注、p. 165)。
NP の言語では、証明者は証拠を 1 回送るだけでよい。乱数を使わない検証者との対話は、何回やりとりしても NP の言語しか認識できない(AB07 Theorem 8.3、p. 148)。ところが検証者が乱数を使い、間違いを小さな確率で許すと、「論理式を満たす割り当てがない」ことや、量化記号を交互に重ねた論理式が正しいことまで納得させられる。鍵は、論理式を有限体上の多項式に書き直し(算術化)、多項式の和を 1 変数ずつ乱数の点で確かめる 和検査プロトコル である。
この記事では、対話証明を定義し、$\mathrm{IP}\subset\mathrm{PSPACE}$ を証明する。次に和検査プロトコルの健全性を証明して、充足する割り当ての個数を対話証明できること(とくに $\mathrm{coNP}\subset\mathrm{IP}$)を示し、最後に変数の次数を下げる線形化の作用素を使って $\mathrm{PSPACE}\subset\mathrm{IP}$ を証明する。量化された論理式の真偽の判定が PSPACE 完全であることと、素数判定が多項式時間でできることはこの記事では証明せずに使う。
以下、$x$ は入力のビット列、$n:=|x|$ とし、多項式時間・多項式の領域は $n$ についていう。PSPACE は、決定的な Turing機械で $n$ の多項式の個数のテープのマスだけを使って判定できる言語のクラスである(計算量理論)。
証明者 $P$ と 検証者 $V$ が共通の入力 $x$ を見ながら交互にビット列を送り合い、最後に $V$ が受理か拒否を出力する手順を 対話 という。$V$ は自分だけが見る一様な乱数の列 $r$ を使う多項式時間の算法で、送る文字列と最後の判定は $x$、$r$、それまでに受け取った文字列で決まる。$P$ は任意の関数でよく、計算能力に制限を置かない。言語 $L$ の 対話証明 とは、やりとりの回数が $n$ の多項式でおさえられ、次の 2 条件を満たす検証者 $V$ のことである。
確率は $V$ の乱数 $r$ についてとる。証明者が乱数を使っても、乱数を固定した証明者の平均になるので、受理の確率の最大値は決定的な証明者で達成される(AB07 Remark 8.6、pp. 149–150)。以下、証明者は決定的とし、それまでの通信の列から次に送る文字列を決める関数とみなす。また $V$ の時間は多項式 $q(n)$ 以下なので、乱数は $q(n)$ ビット、各通信の長さも $q(n)$ 以下としてよい($V$ は長い通信の先頭 $q(n)$ ビットしか読めない)。
$L\in\mathrm{NP}$ なら、証明者が証拠を送り検証者が確かめる対話は対話証明なので、$\mathrm{NP}\subset\mathrm{IP}$ である。グラフの非同型のように、NP に属するかどうかが AB07(2007 年の版、§8.3、p. 150)の時点で分かっていない言語の対話証明もある(ゼロ知識証明 の定理「グラフの非同型の対話証明」)。
$\mathrm{IP}=\mathrm{PSPACE}$ である。
$\mathrm{IP}\subset\mathrm{PSPACE}$ は下の thm-ipp-upper、$\mathrm{PSPACE}\subset\mathrm{IP}$ は下の thm-ipp-tqbf である。$\square$
検証者を固定すると、最善の証明者の受理確率は、対話の木の上で「証明者の番では最大、検証者の番では和」をとる再帰で計算できる。木は指数的に大きいが、深さは多項式なので、深さ優先にたどれば多項式の領域で足りる。
$\mathrm{IP}\subset\mathrm{PSPACE}$ である。
$L$ の対話証明 $V$ を固定する。入力 $x$ について、乱数を $r\in\{0,1\}^{q}$($q:=q(n)$)、やりとりの回数を $2k$($k$ は $n$ の多項式。証明者と検証者が交互に送り、検証者から始まるとしてよい)とする。途中までの通信の列 $h$ について、$R(h)$ を「$h$ のうち検証者が送った文字列が、乱数 $r$ と $h$ のうち証明者が送った文字列から $V$ が実際に送るものと一致する」ような $r$ の集合とする。$N(h)$ を次の再帰で定める。
主張:最善の証明者の受理確率は $N(\emptyset)/2^q$ に等しい。 決定的な証明者 $P$ を固定し、$A_P(h)$ を、$r\in R(h)$ のうち、$h$ から先を $P$ と $V$ が対話して $V$ が受理するものの個数とする。ただし $h$ の証明者の通信が $P$ のものと食い違うときも、$h$ から先は $P$ の規則で続ける。通信の数についての逆向きの帰納法で $A_P(h)\le N(h)$ を示す。$h$ が完全なら定義から等号である。検証者の番なら、$R(h)$ は次の通信 $v$ ごとに $R(hv)$ に分かれるので $A_P(h)=\sum_vA_P(hv)\le\sum_vN(hv)$ である。証明者の番なら、$P$ の送る $m$ について $A_P(h)=A_P(hm)\le N(hm)\le N(h)$ である。よって受理確率 $A_P(\emptyset)/2^q$ は $N(\emptyset)/2^q$ 以下である。逆に、各 $h$ で $N(hm)$ を最大にする $m$ を送る証明者 $P_0$ では、同じ帰納法で $A_{P_0}(h)=N(h)$ となる。証明者は通信の列しか見ないが、$P_0$ の規則も通信の列だけで決まるので、$P_0$ は証明者として許される。
領域. $N(\emptyset)$ を、定義どおりの再帰を深さ優先にたどって計算する。再帰の深さは $2k+1$ で、各段では現在の $h$(長さ $2kq$ 以下)、調べている $v$ か $m$、それまでの和か最大値($2^q$ 以下の整数で $q+1$ ビット)を覚えればよい。末端では $r$ を $2^q$ 通り順に調べ、$V$ を走らせて $r\in R(h)$ かどうかと受理するかを判定する。$V$ は多項式時間なので、その模倣も多項式の領域で済む。全体の領域は $O(k\cdot kq)$ に $V$ の模倣の分を足したもので、$n$ の多項式である。
最後に、$N(\emptyset)\ge\frac23\cdot2^q$ なら受理、そうでなければ拒否する。完全性から $x\in L$ なら最善の証明者の受理確率は $2/3$ 以上で、健全性から $x\notin L$ ならどの証明者でも $1/3$ 以下なので、この判定は正しい。よって $L\in\mathrm{PSPACE}$ である。$\square$
最善の証明者が送るべき文字列は、指数時間の計算になりうるが、多項式の領域で求まる。
以下、$p$ は素数、$\mathbb F_p$ は $p$ 元体(有限体)とする。使う代数の事実は 1 つだけである。
体上の $0$ でない 1 変数多項式で次数が $d$ 以下のものの根は $d$ 個以下である。したがって、次数が $d$ 以下の異なる 2 つの多項式 $s,h\in\mathbb F_p[X]$ について、$a\in\mathbb F_p$ を一様に選ぶと $\Pr[s(a)=h(a)]\le d/p$ である。
前半は $d$ についての帰納法による。$f\ne0$ が根 $a$ をもてば、因数定理により $f=(X-a)f_1$ で $f_1\ne0$ の次数は $d-1$ 以下であり、体には零因子がないので $f$ の根は $a$ と $f_1$ の根に限られる。後半は、$s-h$ が $0$ でなく次数 $d$ 以下なので、$s(a)=h(a)$ となる $a$ は $p$ 個のうち $d$ 個以下である。$\square$
算術化. 変数 $x_1,\dots,x_n$ の論理式 $\varphi$ を、次の規則で整数係数の多項式 $A_\varphi(X_1,\dots,X_n)$ に書き直す:$x_i\mapsto X_i$、$\neg\alpha\mapsto1-A_\alpha$、$\alpha\wedge\beta\mapsto A_\alpha A_\beta$、$\alpha\vee\beta\mapsto1-(1-A_\alpha)(1-A_\beta)$。帰納法により、$b\in\{0,1\}^n$ では $A_\varphi(b)$ は $\varphi(b)$ の真偽(真なら $1$、偽なら $0$)に等しい。各変数 $X_i$ についての次数は、$\varphi$ に $x_i$ が現れる回数以下である。$A_\varphi$ は展開せず式のまま扱えば $\varphi$ と同じ程度の長さで書け、$\mathbb F_p$ の点での値は $\varphi$ の長さと $\log p$ の多項式時間で計算できる。
$\varphi=(x_1\vee x_2)\wedge(\neg x_1\vee x_2)$ では
$$
A_\varphi=\bigl(1-(1-X_1)(1-X_2)\bigr)\bigl(1-X_1(1-X_2)\bigr)
$$
で、$(b_1,b_2)=(0,0),(0,1),(1,0),(1,1)$ での値は $0,1,0,1$ である。よって $\varphi$ を満たす割り当ては $\sum_{b\in\{0,1\}^2}A_\varphi(b)=2$ 個ある。
充足する割り当ての個数は、多項式の $\{0,1\}^n$ 上の和である。和は $2^n$ 項あるので検証者は直接計算できないが、証明者に 1 変数ずつ部分和を送らせ、乱数の点で確かめることができる。
素数 $p$、$\mathbb F_p$ 係数の多項式 $g(X_1,\dots,X_n)$ で各変数についての次数が $d$ 以下のもの、$K\in\mathbb F_p$ が与えられ、検証者は $g$ の $\mathbb F_p^n$ の点での値を計算できるとする。主張
$$
K=\sum_{b_1\in\{0,1\}}\cdots\sum_{b_n\in\{0,1\}}g(b_1,\dots,b_n)\quad(\mathbb F_p\text{ で})
$$
について、$c_0:=K$ とし、$i=1,\dots,n$ の順に次を行う。
$h_i$ は $a_1,\dots,a_{i-1}$ に依存する次数 $d$ 以下の多項式で、定義から
$$
h_1(0)+h_1(1)=\sum_{b\in\{0,1\}^n}g(b),\qquad h_{i+1}(0)+h_{i+1}(1)=h_i(a_i)\quad(1\le i< n)
$$
を満たす。$h_{n+1}(0)+h_{n+1}(1)$ の代わりに $g(a_1,\dots,a_n)=h_n(a_n)$ と約束し、第 $i$ 段の 主張 を「$c_i=h_{i+1}(0)+h_{i+1}(1)$」($i=n$ では「$c_n=g(a_1,\dots,a_n)$」)とする。
完全性. 主張が正しく $s_i=h_i$ なら、$s_1(0)+s_1(1)=K$ で、$i\ge2$ では $s_i(0)+s_i(1)=h_{i-1}(a_{i-1})=c_{i-1}$ なので検査を通り、最後も $c_n=h_n(a_n)=g(a_1,\dots,a_n)$ である。
健全性. 第 $0$ 段の主張が偽とする。任意の証明者を固定し、第 $i-1$ 段の主張が偽であるとして第 $i$ 段を考える。証明者の送る $s_i$ は、それまでの通信、すなわち $a_1,\dots,a_{i-1}$ で決まり、$a_i$ とは独立である。
ex-ipp-arith の $g:=A_\varphi$、$n=2$、$d=2$($x_1,x_2$ はどちらも 2 回現れる)、$p=7$、$K=2$ とする。正直な証明者は $s_1(X)=h_1(X)=A_\varphi(X,0)+A_\varphi(X,1)=X(1-X)+1$ を送り、$s_1(0)+s_1(1)=1+1=2=K$ で検査を通る。検証者が $a_1=3$ を選ぶと $c_1=s_1(3)=-5\equiv2$ である。次に $s_2(X)=A_\varphi(3,X)=(3-2X)(3X-2)\equiv1+6X+X^2\pmod 7$ が送られ、$s_2(0)+s_2(1)=1+8\equiv2=c_1$ である。$a_2=5$ なら $c_2=s_2(5)=56\equiv0$ で、直接の計算 $A_\varphi(3,5)=(1-8)(1+12)\equiv0$ と一致するので受理する。
$\#\mathrm{SAT}_D$ を、論理式 $\varphi$ と整数 $K$ の組で、$\varphi$ を満たす割り当てがちょうど $K$ 個あるものの言語とする。
$\#\mathrm{SAT}_D\in\mathrm{IP}$ である。とくに、充足できない論理式の言語($K=0$ の場合)は $\mathrm{IP}$ に属し、$\mathrm{coNP}\subset\mathrm{IP}$ である(AB07 Theorem 8.18、p. 158)。
入力 $(\varphi,K)$ で、$\varphi$ の変数を $n$ 個、長さを $\ell$ とし、$d:=\ell$、$N:=\max(2^n,3nd)$ とする。検証者は $K< 0$ か $K>2^n$ なら拒否する。証明者は $N< p\le2N$ の素数 $p$ を送る(Bertrandの仮説 により存在する)。検証者は $p$ がこの範囲にあり素数であることを確かめる。素数判定は決定的な多項式時間でできる(AKS素数判定法、素数判定、AB07 §7.2.1、p. 117)。続いて $g:=A_\varphi\bmod p$ で thm-ipp-sumcheck を行う。$p$ は $O(n+\log\ell)$ ビットなので、検証者は多項式時間である。
$0\le K\le2^n< p$ で、満たす割り当ての個数 $\sum_bA_\varphi(b)$ も $0$ 以上 $2^n$ 以下なので、$\mathbb F_p$ での等式は整数としての等式と同値である。よって $(\varphi,K)\in\#\mathrm{SAT}_D$ なら正直な証明者で確率 $1$ で受理し、そうでなければどの証明者でも受理の確率は $nd/p< nd/(3nd)=1/3$ 以下である。$\varphi$ が充足できないことは $(\varphi,0)\in\#\mathrm{SAT}_D$ と同値で、充足可能性は NP 完全なので(Cook–Levinの定理)、coNP のどの言語も多項式時間の帰着でこれに移る。検証者は最初に帰着を計算すればよいので、$\mathrm{coNP}\subset\mathrm{IP}$ である。$\square$
量化された論理式 とは、論理式 $\varphi(x_1,\dots,x_n)$ と量化記号 $Q_i\in\{\forall,\exists\}$ からなる $\psi=Q_1x_1\,Q_2x_2\cdots Q_nx_n\,\varphi$ のことで、変数は $\{0,1\}$ を動く。正しいものの全体を $\mathrm{TQBF}$ と書く。$\mathrm{TQBF}$ は PSPACE 完全である。すなわち $\mathrm{TQBF}\in\mathrm{PSPACE}$ で、PSPACE のどの言語も多項式時間の帰着で $\mathrm{TQBF}$ に移る(AB07 Theorem 4.11、p. 81。この記事では証明しない)。検証者は最初に帰着を計算すればよいので、$\mathrm{TQBF}\in\mathrm{IP}$ を示せば $\mathrm{PSPACE}\subset\mathrm{IP}$ となる。
和の代わりに $\forall$ を積 $A(0)A(1)$、$\exists$ を $1-(1-A(0))(1-A(1))$ で算術化すると、真偽は保たれるが、積をとるたびに残りの変数の次数が倍になり、$n$ 段で $2^n$ 次になって証明者が多項式を送れなくなる。そこで、$\{0,1\}$ の上の値を変えずに次数を $1$ に下げる作用素をはさむ(AB07 Remark 8.19、p. 161)。
変数 $x$ を含む多項式 $F$ について、$F|_{x=c}$ を $x$ に $c$ を代入したものとし、
$$
\forall_xF:=F|_{x=0}\cdot F|_{x=1},\qquad \exists_xF:=1-(1-F|_{x=0})(1-F|_{x=1}),\qquad L_xF:=x\,F|_{x=1}+(1-x)\,F|_{x=0}
$$
と定める。$\forall_x,\exists_x$ は $x$ を消し、$L_x$ は $x$ を残す。
$L_x$ は、$x\in\{0,1\}$ で値を変えず($x=1$ なら $F|_{x=1}$、$x=0$ なら $F|_{x=0}$)、$x$ についての次数を $1$ 以下にし、ほかの変数についての次数を増やさない。量化された論理式 $\psi=Q_1x_1\cdots Q_nx_n\,\varphi$ に、$L_i:=L_{x_i}$ として次の作用素の列を対応させる。
$$
Q_1x_1\;L_1\;\;Q_2x_2\;L_1L_2\;\;Q_3x_3\;L_1L_2L_3\;\cdots\;Q_nx_n\;L_1L_2\cdots L_n
$$
ここで $Q_ix_i$ は作用素 $\forall_{x_i}$ か $\exists_{x_i}$ を表す。作用素の個数は $k:=n+n(n+1)/2$ で、左から $O_1,\dots,O_k$ と書く。$F_{k+1}:=A_\varphi$、$F_j:=O_jF_{j+1}$ と右から順に作用させ、$F_1$ を得る。$F_1$ には自由な変数がない。
$\ell$ を $\varphi$ の長さ、$D:=\max(2,\ell)$ とする。
1. 右から順に、$F_j$ の自由な変数に $\{0,1\}$ の値を入れると、その値は、$O_j$ 以降で最初の量化記号を $Q_ix_i$ として、論理式 $Q_ix_i\cdots Q_nx_n\varphi$ の真偽に等しいことを示す(量化記号がなければ $\varphi$ の真偽)。$j=k+1$ では算術化の性質である。$O_j=L_x$ なら、上の注意により $\{0,1\}$ の上で値は $F_{j+1}$ と同じである。$O_j=\forall_{x}$ なら、$F_{j+1}|_{x=0}$ と $F_{j+1}|_{x=1}$ はそれぞれ $x=0,1$ を入れた論理式の真偽で、$\{0,1\}$ の値の積は「かつ」を表す。$\exists_x$ では $1-(1-u)(1-v)$ が「または」を表す。$j=1$ で自由な変数がなくなり、主張を得る。
2. $O_j=Q_ix_i$ のとき、$F_{j+1}$ は $L_1\cdots L_i$ を最後に作用させたものなので、$x_i$ について次数 $1$ 以下である。$O_j=L_t$ が $Q_ix_i$ の直後の組 $L_1\cdots L_i$ に属すとき($t\le i$)、$F_{j+1}$ は、$i< n$ なら $G:=Q_{i+1}x_{i+1}H$($H$ は $L_1\cdots L_{i+1}$ を作用させたもので $x_t$ について次数 $1$ 以下)にいくつかの $L$ を作用させたもの、$i=n$ なら $A_\varphi$ にいくつかの $L$ を作用させたものである。$G$ は $H$ の 2 つの代入の積を含むので $x_t$ について次数 $2$ 以下、$A_\varphi$ は $x_t$ について次数 $\ell$ 以下で、$L$ はほかの変数についての次数を増やさない。よって次数は $D$ 以下である。$\square$
$\mathrm{TQBF}\in\mathrm{IP}$ である。したがって $\mathrm{PSPACE}\subset\mathrm{IP}$ である。さらに、正しい論理式では確率 $1$ で受理する証明者がある。
入力 $\psi$ について $k,D$ を上のとおりとし、検証者は $3kD< p\le6kD$ の素数 $p$ を試し割りで見つけて固定する(Bertrandの仮説 により存在し、$kD$ は入力の長さの多項式なので多項式時間でできる)。以下 $\mathbb F_p$ で計算する。各段の 主張 は「$F_j(a)=c$」の形で、$a$ は $F_j$ の自由な変数への $\mathbb F_p$ の値の割り当て、$c\in\mathbb F_p$ である。最初の主張は「$F_1=1$」である。$j=1,\dots,k$ の順に、$O_j$ が作用する変数を $x$ として次を行う。
完全性. $h$ の定義と def-ipp-operators から、$F_j(a)$ は $h$ を使って手順 2 の式で表される。よって主張が正しく $s=h$ なら手順 2 の検査を通り、$s(r)=h(r)=F_{j+1}(a')$($a'$ は新しい割り当て)なので次の主張も正しい。$\psi$ が正しければ、lem-ipp-operators の 1 から最初の主張「$F_1=1$」は正しく、最後まで正しいまま受理される。
健全性. $\psi$ が正しくなければ $F_1=0\ne1$ で、最初の主張は偽である($p>2$)。任意の証明者について、第 $j$ 段の主張が偽とする。$s=h$ なら、手順 2 の式の左辺は $F_j(a)$ に等しく $c$ と異なるので拒否される。$s\ne h$ なら、lem-ipp-operators の 2 から $s,h$ はともに次数 $D$ 以下で、次の主張が正しくなるのは $s(r)=h(r)$ のときに限り、その確率は lem-ipp-roots により $D/p$ 以下である。受理されるには最後の主張が正しくなければならないので、prf-ipp-sumcheck と同じく、受理の確率は $kD/p< kD/(3kD)=1/3$ 以下である。
時間. $p$ のビット数は $O(\log(kD))$ で、各段の検査、乱数の選択、最後の $A_\varphi(a)$ の計算は多項式時間である。段数 $k$ は $n$ の 2 次式である。よって検証者は多項式時間で、これは $\mathrm{TQBF}$ の対話証明である。$\square$
$\{0,1\}$ の上で値が $0$ か $1$ なので、$F_1$ は整数としても $0$ か $1$ であり、#SAT の場合と違って大きな素数は要らない。thm-ipp-upper と合わせて thm-ipp-main が得られる。正直な証明者が送る多項式も多項式の領域で計算でき、これを使うと、PSPACE が多項式の大きさの回路の族で計算できるなら $\mathrm{PSPACE}=\mathrm{MA}$ となる(AB07 §8.6 と Theorem 8.20、pp. 161–162)。
次の表の 1〜3 行は thm-ipp-sumcheck と cor-ipp-sharpsat の仮定を 1 つ外したもので、どれも誤った主張を確率 $1$ またはそれに近い確率で受理させる。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| $a_i$ を $s_i$ が送られた後に一様に選ぶ | $p=5$、$g=X_1X_2$(正しい和は $1$)、偽の $K=2$、$a_1=0$ を証明者が前もって知る | 健全性。$s_1:=2X$ は $s_1(0)+s_1(1)=2$ を通り、$c_1=s_1(0)=0=h_2(0)+h_2(1)$ で以後は正しい主張になり、確率 $1$ で受理される |
| $s_i$ の次数が $d$ 以下 | $p=7$、ex-ipp-arith の $g$(正しい和は $2$)、偽の $K=5$、$s_1:=h_1+3(1-X^{6})$ | 健全性。$s_1(0)+s_1(1)=5$ を通り、$s_1$ は $h_1$ と $X=0$ 以外の $6$ 点で一致する。$a_1\ne0$ なら以後は正しい主張なので、受理の確率は $6/7$ 以上 |
| $p>2^n$(cor-ipp-sharpsat) | $n=10$ 変数 $x_1,\dots,x_{10}$ の $\varphi=x_1\vee\neg x_1$(満たす割り当ては $1024$ 個。$\varphi$ の長さ $\ell$ について $3nd=30\ell< p$)、$p=1021$、偽の $K=3$ | $1024\equiv3\pmod{1021}$ なので、正直に $\bmod 1021$ の和を確かめる証明者で確率 $1$ で受理される |
| 検証者が乱数を使う | 乱数を使わない検証者 | 対話証明をもつ言語は NP の言語に限られる(AB07 Theorem 8.3、p. 148)。$\mathrm{NP}=\mathrm{PSPACE}$ でないかぎり $\mathrm{PSPACE}$ と一致しない |
1 行目の $s_1=2X$ は $h_1(X)=\sum_{b_2}Xb_2=X$ に $X$ を足したもので、$s_1(0)=h_1(0)$ を保ったまま $s_1(0)+s_1(1)$ を $1$ だけずらしている。$a_1$ が前もって分かれば、その点で $h_1$ と一致するように $s_1$ を作れる。2 行目は、次数の制限がなければ $s_1-h_1$ が $p-1$ 個の根をもてることによる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する