Utrzymanie wartości wielomianu nad dynamicznie aktualizowanym wejściem

10

Niech będzie wielomianem nad ustalonym skończonym polem. Załóżmy, że podano nam wartość w pewnym wektorze i wektorze . $P(x_1, x_2, \ldots, x_n)$ $P$ $y \in \{0,1\}^n$ $y$

Teraz chcemy obliczyć wartość na wektorze taki sposób, że i różnią się dokładnie w jednej pozycji (innymi słowy, odwracamy dokładnie jeden bit w ). Jaka jest przestrzeń i czas kompromisów dla tego problemu? $P$ $y' \in \{0,1\}^n$ $y$ $y'$ $y$

Na przykład, jeśli jest liczbą jednomianów w , można przechowywać współczynniki i wartości wszystkich jednomianów w . Jeśli jest odwrócone, ustalamy wartość każdego monomialu zawierającego a następnie wartość podstawie zapisanych informacji. Ogólnie potrzebujemy czasu i przestrzeni. $r$ $P$ $P$ $y_i$ $y_i$ $P(y)$ $O(r)$

(Nie mówię nic o tym, jak celowo identyfikujemy monomialy zawierające . Możesz wybrać dowolną rozsądną reprezentację , w przykładzie zakładam, że przechowujemy listę monomialów zawierających dla każdego .) $y_i$ $P$ $y_i$ $i$

Czy jest coś lepszego?

polynomials dynamic-algorithms Tatiana Starikovskaya
źródło

7

Twój pomysł uogólnia się następująco: biorąc pod uwagę obwód algebraiczny (nad polem skończonym) lub obwód boolowski (obliczając bitową reprezentację elementów pola skończonego) obliczając , a następnie zachowując wartość na każdej bramce w obwodzie. Kiedy zmieniasz -ty bit , po prostu propaguj tę zmianę wzdłuż DAG obwodu, zaczynając od wejścia . Jeśli obwód ma rozmiar , zajmuje to czas i przestrzeń. Może to być znacznie mniejsza niż liczba monomialów (co odpowiada wielkości algebraicznych obwodów o głębokości tylko 2). $P$ $i$ $y$ $y_i$ $s$ $O(s)$

Joshua Grochow
źródło

1

Nie jestem pewien, czy było to celowe, ale problem nie mówi, że otrzymaliśmy

, tylko

.

y

$y$

f (y)

$f(y)$

Andrew Morgan

1

@AndrewMorgan Zależy od twojej aplikacji, dla mojej można założyć, że podano ci y. Dziękuje za komentarz!

Tatiana Starikovskaya

2

@AndrewMorgan: Rzeczywiście, chociaż jest to technicznie prawdą, sposób, w jaki sformułowano przykładową konstrukcję w OQ, domyślnie zakłada, że podano

. Jeśli nie podano

, myślę, że problem ten staje się znacznie trudniejszy. (Tatiana, warto dodać to jako wyjaśnienie pytania).

y

$y$

y

$y$

Joshua Grochow

5

Łatwo jest zmodyfikować sposób przechowywania monomialów, tak aby każda aktualizacja trwała tylko proporcjonalnie do liczby zmienionych monomialów: wystarczy zaktualizować całkowitą wartość wielomianową, dodając nową wartość i odejmując starą wartość dla każdego zmienionego monomialu.

Jeśli masz formułę do odczytu (tj. Każda zmienna pojawia się na jednym liściu drzewa formuły, a każdy węzeł wewnętrzny jest operacją arytmetyczną z dwoma wejściami, jak plus lub razy), możesz zachować wartość w logarytmii czas na aktualizację za pomocą drzewa kompresji prowizji nad formułą. Stosując to podejście do dowolnej formuły, czas na aktualizację zmiennej, która pojawia się razy, będzie wynosił gdzie jest rozmiarem formuły. Tak więc, z wyjątkiem współczynnika logarytmicznego, uogólnia on granicę liczby zmienionych jednomianów i stosuje się do bardziej ogólnych typów rozszerzania wielomianu do formuły. $P$ $P$ $k$ $O(k\log N)$ $N$

David Eppstein
źródło

Utrzymanie wartości wielomianu nad dynamicznie aktualizowanym wejściem

Odpowiedzi: