多項式恒等式判定

数学において、多項式同一性判定（PIT ）とは、2つの多変数多項式が同一であるかどうかを効率的に判定する問題である。より厳密に言えば、PITアルゴリズムは、体上の多項式pを計算し、pが零多項式であるかどうかを判定する算術回路を与えられる。多項式同一性判定に必要な計算複雑性を決定すること、特にPITの決定論的アルゴリズムを見つけることは、代数的複雑性理論における最も重要な未解決問題の一つである。

質問「${\displaystyle (x+y)(xy)}$等しい${\displaystyle x^{2}-y^{2}}$？は、2 つの多項式が同一であるかどうかについての質問です。他の多項式の同一性テスト問題と同様に、これは「ある多項式は 0 に等しいか？」という質問に簡単に変換できます。この場合、「${\displaystyle (x+y)(xy)-(x^{2}-y^{2})=0}$? 多項式が代数式として与えられた場合（ブラックボックスとしてではなく）、総当たり乗算と加算によって等式が成り立つことを確認できますが、総当たりアプローチの時間計算量は次のように増加します。${\displaystyle {\tbinom {n+d}{d}}}$、 どこ${\displaystyle n}$は変数の数です（ここでは、${\displaystyle n=2}$:${\displaystyle x}$は最初であり、${\displaystyle y}$は2番目であり、${\displaystyle d}$は多項式の次数です（ここでは、${\displaystyle d=2}$）。 もし${\displaystyle n}$そして${\displaystyle d}$どちらも大きい、${\displaystyle {\tbinom {n+d}{d}}}$指数関数的に増加する。^{[ 1 ]}

PIT は、多項式がゼロ多項式と同一であるかどうかに関係し、与えられた領域で多項式によって実装される関数が常にゼロに評価されるかどうかには関係しません。たとえば、2 つの要素を持つ体GF(2)には、要素 0 と 1 のみが含まれます。GF(2) では、${\displaystyle x^{2}-x}$常にゼロと評価されるが、PIT はこれを考慮しない。${\displaystyle x^{2}-x}$ゼロ多項式と等しくなる。^{[ 2 ]}

多項式恒等式判定に必要な計算複雑性を決定することは、「代数的計算複雑性」として知られる数学のサブ分野における最も重要な未解決問題の 1 つです。^{[ 1 ] [ 3 ]} PIT の研究は、 IP = PSPACEの証明など、計算複雑性の他の多くの分野の基礎となっています。^{[ 1 ] [ 4 ]}さらに、PIT はTutte 行列や素数判定にも応用されており、PIT 技術は素数判定のための最初の決定論的 (ただし実用的ではない)多項式時間アルゴリズムであるAKS 素数判定につながりました。^{[ 1 ]}

体における多項式を計算する算術回路が与えられたとき、その多項式がゼロ多項式（つまり、非ゼロ項を持たない多項式）と等しいかどうかを判定する。^{[ 1 ]}

場合によっては、算術回路の仕様がPITソルバーに与えられず、PITソルバーは回路を実装する「ブラックボックス」に値を入力し、その出力を解析することしかできません。以下の解法は、与えられた体におけるあらゆる演算（乗算など）が定数時間で完了することを前提としています。さらに、以下のすべてのブラックボックスアルゴリズムは、体のサイズが多項式の次数よりも大きいことを前提としています。

シュワルツ・ジッペルアルゴリズムは、入力をランダムにテストし、出力がゼロかどうかをチェックするだけで、実用的な確率的解法を提供します。これは、正しさが証明された最初のランダム化多項式時間PIT アルゴリズムでした。 ^{[ 1 ]}入力が抽出される領域が大きいほど、シュワルツ・ジッペルが失敗する可能性は低くなります。ランダムビットが不足している場合は、チェン・カオアルゴリズム (有理数上) またはレウィン・ヴァダンアルゴリズム (任意の体上) は、実行時間の増加を伴うものの、より少ないランダムビットを必要とします。^{[ 2 ]}

疎なPITは最大で${\displaystyle m}$非ゼロの単項式項。疎な PIT は、回路のサイズと数の多項式時間で決定論的に解くことができます。${\displaystyle m}$単項式の^{[ 1 ]}も参照。^{[ 5 ]}

低次数PITには、多項式の次数に上限があります。任意の低次数PIT問題は、回路サイズの準指数時間で深さ4の回路のPIT問題に還元できます。そのため、深さ4（およびそれ以下）の回路のPITは集中的に研究されています。^{[ 1 ]}

• シュワルツ・ジッペル補題の応用

• 「シュワルツ・ジッペル補題による多項式の恒等式判定」に関する講義ノート
• マイケル・フォーブスによる多項式恒等式判定法 - MIT（YouTube）
• 多項式恒等式テスト部門の受賞者