Maintenir la valeur d'un polynôme sur une entrée mise à jour dynamiquement

Soit un polynôme sur un champ fini fixe. Supposons qu'on nous donne la valeur de P sur un vecteur y ∈ { 0 , 1 } n et le vecteur y .$P(x_1, x_2, \ldots, x_n)$$P$$y \in \{0,1\}^n$$y$

Nous voulons maintenant calculer la valeur de sur un vecteur y ′ ∈ { 0 , 1 } n de telle sorte que y et y ′ diffèrent sur exactement une position (en d'autres termes, nous inversons exactement un bit en y ). Quels sont l'espace et les compromis temporels pour ce problème?$P$$y' \in \{0,1\}^n$$y$$y'$$y$

Par exemple, si est le nombre de monômes en P , nous pouvons stocker les coefficients et les valeurs de tous les monômes en P . Si y i est inversé, nous fixons la valeur de chaque monôme contenant y i puis la valeur de P ( y ) en utilisant les informations stockées. Dans l'ensemble, nous avons besoin de temps et d'espace O ( r ) .$r$$P$$P$$y_i$$y_i$$P(y)$$O(r)$

(Je ne dis rien sur la façon dont nous identifions les monômes contenant à des fins spécifiques. Vous pouvez choisir n'importe quelle représentation raisonnable de P , dans l'exemple, je suppose que nous stockons une liste de monômes contenant y i pour chaque i .)$y_i$$P$$y_i$$i$

Y a-t-il quelque chose de mieux?

Votre idée se généralise comme suit: étant donné un circuit algébrique (sur le champ fini) ou un circuit booléen (calculant la représentation bit à bit de vos éléments de champ fini) calculant , puis maintenez la valeur à chaque porte du circuit. Lorsque vous modifiez le i- ème bit de y , propagez simplement ce changement le long du DAG du circuit, en commençant par l'entrée y i . Si le circuit a une taille s , cela prend du temps et de l'espace O ( s ) . Cela pourrait être beaucoup plus petit que le nombre de monômes (ce qui correspond à la taille des circuits algébriques de profondeur seulement 2).$P$$i$$y$$y_i$$s$$O(s)$

Il est facile de modifier votre approche de stockage des monômes afin que chaque mise à jour ne prenne du temps que proportionnellement au nombre de monômes modifiés: il suffit de mettre à jour la valeur totale du polynôme en ajoutant la nouvelle valeur et en soustrayant l'ancienne valeur pour chaque monôme modifié.

$P$$P$$k$$O(k\log N)$$N$