Encuentra un polinomio en dos o tres consultas

El recuadro negro de significa que puedo evaluar el polinomio en cualquier punto. $f(x)$ $f(x)$

Entrada : Una caja negra de polinomio monico de grado . $f(x) \in\mathbb{Z}^+[x]$ $d$
Salida: Los coeficientes de polinomio . $d$ $f(x)$

Mi algoritmo: let

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$

Evalúe el polinomio en muchos puntos usando el cuadro negro y obtenga un sistema de ecuaciones lineales. Ahora puedo resolver el sistema de ecuaciones lineales para obtener los coeficientes deseados. $\mathcal{f(x)}$ $d$

Sin embargo, en este caso, necesito muchas consultas al cuadro negro. Quiero minimizar la cantidad de consultas . ¿Hay alguna forma de reducir el número de consultas a solo dos o tres? $\mathcal{O(d)}$

algorithms polynomials Complejidad
fuente

Sigues cambiando la pregunta. Quizás primero deba decidir sobre su pregunta y solo luego formularla. De lo contrario, puede ser algo frustrante para el que responde.

Yuval Filmus

¿Qué significa ?

Z^{+}

$\mathbb{Z}^+$

md5

conjunto de enteros positivos

Complejidad

Por cierto para su algoritmo, los coeficientes se pueden calcular en lugar de con la fórmula cerrada de Lagrange.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

md5

Exactamente la misma pregunta, redactada de manera diferente: math.stackexchange.com/questions/446130/…

Nayuki

Respuestas:

Puede determinar el polinomio usando dos consultas. Primero consulte el polinomio en para obtener un límite superior en el valor de los coeficientes. Ahora consulte el polinomio en de su elección y lea los coeficientes de la expansión base . $x=1$ $M$ $x > M$ $x$

Curiosamente, si permite que los coeficientes sean negativos, entonces no puede hacerlo mejor que consultas. De hecho, siempre puedo responder a sus consultas por cero, y esto no fija el valor del polinomio ya que todos los polinomios de la forma $d$ $d-1$ $x_1,\ldots,x_{d-1}$ son consistentes con mis respuestas. $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Yuval Filmus
fuente

Para los negativos, creo que el truco del complemento 2 puede funcionar.

Complejidad

No sin un límite superior en la magnitud de los coeficientes. Esto es lo que muestra mi prueba.

Yuval Filmus el

Lo siento, no obtuve esta parte "Siempre puedo responder a tus consultas

d - 1

$d-1$

por cero"

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

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

Complejidad

Este es un argumento adversario. Su algoritmo le pide a la caja negra el valor de

f

$f$

d - 1

$d-1$ lugares, y siempre responde cero. Demuestro que esto no es suficiente para deducir el valor de

f

$f$

Yuval Filmus