Trouver un polynôme en deux ou trois requêtes

La boîte noire de $f(x)$ signifie que je peux évaluer le polynôme $f(x)$ à tout moment.

Entrée : Une boîte noire de polynôme monique de degré . $f(x) \in\mathbb{Z}^+[x]$ $d$
Sortie: les coefficients du polynôme . $d$ $f(x)$

Mon algorithme: laissez

f (x) = x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{1} x + a_{0}

$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$

Évaluez le polynôme en plusieurs points à l'aide de la boîte noire et obtenez un système d'équations linéaires. Maintenant, je peux résoudre le système d'équations linéaires pour obtenir les coefficients souhaités. $\mathcal{f(x)}$ $d$

Cependant, dans ce cas, j'ai besoin de nombreuses requêtes dans la boîte noire. Je souhaite minimiser le nombre de requêtes . Existe-t-il un moyen de réduire le nombre de requêtes à seulement deux ou trois? $\mathcal{O(d)}$

algorithms polynomials Complexité
la source

Vous continuez de changer la question. Vous devriez peut-être d'abord décider de votre question et ensuite seulement la poser. Sinon, cela peut être quelque peu frustrant pour le répondeur.

Yuval Filmus

Que signifie

Z^{+}

$\mathbb{Z}^+$

md5

ensemble d'entiers positifs

Complexité

BTW pour votre algorithme, les coefficients peuvent être calculés en

au lieu de

avec la formule fermée de Lagrange.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

md5

Exactement la même question, formulée différemment: math.stackexchange.com/questions/446130/…

Nayuki

Réponses:

Vous pouvez déterminer le polynôme à l'aide de deux requêtes. Recherchez d'abord le polynôme à pour obtenir une borne supérieure sur la valeur des coefficients. Maintenant interrogez le polynôme à de votre choix et lisez les coefficients de l' expansion de base . $x=1$ $M$ $x > M$ $x$

Curieusement, si vous autorisez les coefficients à être négatifs, vous ne pouvez pas faire mieux que requêtes. En effet, je peux toujours répondre à vos requêtes par zéro, et cela ne fixe pas la valeur du polynôme puisque tous les polynômes de la forme sont conformes à mes réponses. $d$ $d-1$ $x_1,\ldots,x_{d-1}$ $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Yuval Filmus
la source

Pour les négatifs, je pense que le genre de truc du complément 2 peut fonctionner.

Complexité

Non sans limite supérieure de l'amplitude des coefficients. C'est ce que montre ma preuve.

Yuval Filmus

Désolé , je n'ai pas eu cette partie « Je peux toujours répondre à votre

requêtes

par zéro »

d - 1

$d-1$

x_{1}, \dots, x_{d - 1}

$x_1,\ldots,x_{d-1}$

complexité

C'est un argument adversaire. Votre algorithme demande à la boîte noire la valeur de

endroits, et il répond toujours à zéro. Je montre que cela ne vous suffit pas pour déduire la valeur de

f

$f$

d - 1

$d-1$

f

$f$

Yuval Filmus