Mempertahankan nilai polinomial dari input yang diperbarui secara dinamis

Biarkan menjadi polinomial di atas bidang hingga yang tetap. Misalkan kita diberi nilai pada beberapa vektor dan vektor .P y ∈ { 0 , 1 } n$P(x_1, x_2, \ldots, x_n)$$P$$y \in \{0,1\}^n$$y$

Kami sekarang ingin menghitung nilai pada vektor sehingga dan berbeda pada satu posisi yang tepat (dengan kata lain, kami membalik tepat satu bit dalam ). Apa ruang dan waktu trade-off untuk masalah ini?y ′ ∈ { 0 , 1 } n y y ′$P$$y' \in \{0,1\}^n$$y$$y'$$y$

Sebagai contoh, jika adalah jumlah monomials di , kita dapat menyimpan koefisien dan nilai-nilai semua monomials di . Jika dibalik, kami memperbaiki nilai setiap monomial yang mengandung dan kemudian nilai menggunakan informasi yang disimpan. Secara keseluruhan, kita membutuhkan waktu dan ruang.P P y i y i P ( y ) O ( r $r$$P$$P$$y_i$$y_i$$P(y)$$O(r)$

(Saya tidak mengatakan apa-apa tentang bagaimana kami mengidentifikasi monomial yang mengandung untuk tujuan. Anda dapat memilih representasi masuk akal , dalam contoh saya berasumsi bahwa kami menyimpan daftar monomial yang berisi untuk setiap .) P y i$y_i$$P$$y_i$$i$

Apa ada yang lebih bagus?

Ide Anda menggeneralisasi sebagai berikut: diberi sirkuit aljabar (di atas bidang hingga) atau sirkuit Boolean (menghitung representasi bit-bijaksana dari elemen bidang hingga Anda) menghitung , kemudian mempertahankan nilai di setiap gerbang di sirkuit. Ketika Anda mengubah bit ke- i dari y , cukup rentangkan perubahan itu di sepanjang DAG rangkaian, mulai dari input y i . Jika rangkaian memiliki ukuran s , ini mengambil O ( s ) ruang dan waktu. Ini bisa jauh lebih kecil dari jumlah monomial (yang sesuai dengan ukuran sirkuit aljabar hanya 2).$P$$i$$y$$y_i$$s$$O(s)$

Sangat mudah untuk memodifikasi pendekatan penyimpanan monomial Anda sehingga setiap pembaruan hanya memakan waktu yang sebanding dengan jumlah monomial yang diubah: perbarui saja nilai polinom total dengan menambahkan nilai baru dan kurangi nilai lama untuk setiap monomial yang diubah.

Jika Anda memiliki rumus baca-sekali untuk (yaitu setiap variabel muncul pada satu daun dari pohon rumus, dan setiap simpul internal adalah operasi aritmatika dua-input seperti plus atau kali) maka Anda dapat mempertahankan nilai P dalam logaritmik waktu per pembaruan menggunakan pohon kompres menyapu di atas rumus. Menerapkan pendekatan ini ke rumus sewenang-wenang, waktu untuk memperbarui variabel yang muncul k kali adalah O ( k log N ) di mana N adalah ukuran rumus. Jadi kecuali untuk faktor log, ini menggeneralisasi batas untuk jumlah monomial yang berubah, dan berlaku untuk jenis ekspansi polinomial yang lebih umum ke dalam formula.$P$$P$$k$$O(k\log N)$$N$