Bukankah pengujian identitas polinomial lebih dari aritmatika * ekspresi * sepele?

Pengujian identitas polinomial adalah contoh standar masalah yang diketahui berada di co-RP tetapi tidak diketahui berada di P . Lebih dari rangkaian aritmatika , memang tampak sulit, karena tingkat polinom dapat dibuat besar secara eksponensial dengan kuadrat ulang. Pertanyaan ini membahas masalah bagaimana mengatasi ini dan menjaga masalah dalam waktu polinomial acak.

Di sisi lain, ketika masalah awalnya disajikan (misalnya di sini ), sering diilustrasikan pada ekspresi aritmatika yang hanya berisi konstanta, variabel, penambahan, dan perkalian. Polinomial semacam itu memiliki derajat total paling banyak polinomial dalam panjang ekspresi input, dan untuk polinomial semacam itu ukuran nilai output polinomial dalam ukuran nilai input. Tapi karena jumlahnya banyak dari derajat memiliki paling akar, bukankah ini sepele? Hanya mengevaluasi polinomial atas rationals di setiap$d$$d$ $d + 1$titik yang berbeda dan periksa apakah hasilnya nol di setiap titik. Ini seharusnya hanya memakan waktu polinomial. Apakah ini benar? Jika demikian, mengapa ekspresi aritmatika tanpa subekspresi bersama sering digunakan sebagai contoh, ketika berbagi sangat penting untuk kesulitan masalah?

Itu tidak diketahui sepele .

Polinomial memiliki tak terhingga banyaknya akar. (Ketika salah satu variabel nol, variabel lainnya tidak akan mempengaruhi nilai polinomial.)$x \cdot y$

Untuk polinomial univariat$p(x)$ya itu mudah.

Untuk polinomial multivarian$p(x_1,x_2,\dots,x_k)$, tidak, tidak ada algoritma yang berfungsi.

Secara khusus, ketika Anda menulis "polinomial derajat $d$ paling banyak $d$ root ", itu berlaku untuk polinomial univariat $p(x)$, tetapi itu tidak benar secara umum untuk polinomial multivariat. Ricky Demer memberikan contoh sederhana:$p(x,y) = xy$ adalah dari tingkat dua, tetapi memiliki banyak akar yang tak terhingga.

Inilah cara yang lebih umum / abstrak untuk memahami pentingnya / kekerasan pengujian identitas polinomial dalam CS. salah satu alasan pengujian identitas polinomial sedang dalam penelitian intensif sekarang karena telah lama diketahui terkait erat dengan kompleksitas sirkuit boolean. bayangkan mengambil dua sirkuit boolean sembarang dan kemudian mengubahnya (yaitu pada dasarnya membuat pemetaan 1-1) untuk polinomial multivarian. ini tidak terlalu sulit. pada dasarnya kita menggunakan nilai 0/1 untuk mewakili false / true dan konstruksinya diatur dalam kertas lama. maka akar polinomial berhubungan dengan penugasan variabel T / F yang memenuhi rumus / sirkuit.

setelah pengaturan ini, PIT pada dasarnya masalah yang hampir sama dengan menentukan apakah dua sirkuit biner setara. ada juga bukti mendalam (baru) lainnya yang mengatakan bahwa kompleksitasnya hampir setara dengan polinomial anjak [ 1 ] sehingga seseorang berakhir dengan hasil seperti berikut: jika seseorang dapat memecahkan PIT "dengan cepat" itu berarti bahwa dua sirkuit besar dapat dibandingkan dengan kesetaraan "cepat" yang tidak mungkin. jadi cara kasar untuk memahami masalah adalah bahwa hampir setara dengan masalah nontrivial dalam teori sirkuit boolean.