Encuentra un polinomio en dos o tres consultas

17

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)Z+[x]d

  • Salida: Los coeficientes de polinomio .df(x)

Mi algoritmo: let

f(x)=xd+ad1xd1++a1x+a0

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.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?O(d)

Complejidad
fuente
2
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
2
¿Qué significa ? Z+
md5
1
conjunto de enteros positivos
Complejidad
1
Por cierto para su algoritmo, los coeficientes se pueden calcular en lugar de con la fórmula cerrada de Lagrange. O ( n 3 )O(n2)O(n3)
md5
2
Exactamente la misma pregunta, redactada de manera diferente: math.stackexchange.com/questions/446130/…
Nayuki

Respuestas:

29

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

Curiosamente, si permite que los coeficientes sean negativos, entonces no puede hacerlo mejor que consultas. De hecho, siempre puedo responder a sus consultas d - 1 x 1 , , x d - 1 por cero, y esto no fija el valor del polinomio ya que todos los polinomios de la forma ( x - x 1 )rere-1X1,...,Xre-1 son consistentes con mis respuestas.(xx1)(xxd1)(xxd)

Yuval Filmus
fuente
Para los negativos, creo que el truco del complemento 2 puede funcionar.
Complejidad
44
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 x 1 , , xd1 por cero"x1,,xd1
Complejidad
66
Este es un argumento adversario. Su algoritmo le pide a la caja negra el valor de en d - 1fd1 lugares, y siempre responde cero. Demuestro que esto no es suficiente para deducir el valor de . f
Yuval Filmus