Polynomial identity testing とは

数学では、多項式同定テスト(PIT)は、2つの多変量多項式が同一かどうかを効率的に決定する問題です。より形式的には、PITアルゴリズムは、フィールド内の多項式pを計算し、pがゼロ多項式であるかどうかを決定する算術回路を与えられる。多項式同定テストに必要な計算量を決定することは、代数的計算の複雑さにおいて最も重要な未解決の問題の1つです。