Memeriksa apakah faktor polinomial menjadi faktor linier

Biarkan $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ menjadi polinomial yang diberikan oleh sirkuit aritmatika $C$ ukuran . Diberikan sebagai input, apakah ada algoritma deterministik untuk memeriksa apakah semua faktor irreducible dari di adalah bentuk linear? Pada catatan terkait, diberikan bentuk linier , dapatkah kita memeriksa secara deterministik apakah merupakan faktor dariC f Q [ x 1 , x $s$$C$$f$l = ∑ n i = 1 l i ⋅ x i l f f $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$$l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$$l$$f$. Tentu saja, kami ingin menjalankan waktu menjadi polinomial dalam kedua kasus. Dengan ukuran, yang kami maksud adalah ukuran total bit. Juga, dapat diasumsikan bahwa derajat adalah polinomial dalam .$f$$n$

Sejauh yang saya tahu, algoritma terbaik yang kami miliki saat ini untuk memeriksa apakah (diberikan oleh rangkaian aritmatika) dapat difaktorkan menjadi faktor linier adalah melalui algoritma acak Kaltofen (PDF) yang benar-benar menghasilkan kotak hitam untuk semua faktor tak tereduksi dari f. , dan bekerja pada bidang yang cukup besar. Faktanya, masalah faktorisasi polinomial untuk sirkuit umum baru-baru ini ditunjukkan oleh Kopparty, Saraf, dan Shpilka setara dengan masalah blackbox-PIT untuk sirkuit umum.$f$$f$

Seperti yang disebutkan oleh Bruno, jika Anda tertarik untuk memeriksa sirkuit yang diberikan dapat dibagi dengan yang diberikan , maka ini berkurang menjadi masalah PIT tertentu. Kami tidak tahu bagaimana melakukan ini secara deterministik secara umum, tetapi saya tahu satu kasus khusus di mana kami tahu bagaimana melakukan PIT ini. Ada algoritma poli-waktu deterministik (PDF) untuk memeriksa apakah suatu ℓ membagi polinomial jarang f .$\ell$$\ell$$f$

$f$$f \bmod \ell$