Encontre um polinômio em duas ou três consultas

A caixa preta de $f(x)$ significa que posso avaliar o polinômio a qualquer momento. $f(x)$

Entrada : Uma caixa preta do polinômio monônico de grau . $f(x) \in\mathbb{Z}^+[x]$ $d$
Saída: Os coeficientes do polinômio . $d$ $f(x)$

Meu algoritmo: deixe

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$

Avalie polinomial em muitos pontos usando a caixa preta e obtenha um sistema de equações lineares. Agora eu posso resolver o sistema de equações lineares para obter os coeficientes desejados. $\mathcal{f(x)}$ $d$

No entanto, nesse caso, preciso de muitas consultas na caixa preta. Eu quero minimizar o número de consultas . Existe alguma maneira de reduzir o número de consultas para apenas duas ou três? $\mathcal{O(d)}$

algorithms polynomials Complexidade
fonte

Você continua mudando a questão. Talvez você deva primeiro decidir sua pergunta e só então perguntar. Caso contrário, pode ser um pouco frustrante para o atendedor.

Yuval Filmus 13/10

O que significa

Z^{+}

$\mathbb{Z}^+$

Md5 #

conjunto de números inteiros positivos

Complexidade

BTW para o seu algoritmo, os coeficientes podem ser calculados em

vez de

com a fórmula fechada de Lagrange.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

Md5 #

Exatamente a mesma pergunta, com a seguinte redação

Nayuki 14/17

Respostas:

Você pode determinar o polinômio usando duas consultas. Primeiro, consulte o polinômio em para obter um limite superior no valor dos coeficientes. Agora consulte o polinômio em de sua escolha e leia os coeficientes da expansão base . $x=1$ $M$ $x > M$ $x$

Curiosamente, se você permitir que os coeficientes sejam negativos, não poderá fazer melhor que consultas. Na verdade, eu sempre posso responder às suas consultas por zero, e isso não fixa o valor do polinômio, pois todos os polinômios da forma são consistentes com minhas respostas. $d$ $d-1$ $x_1,\ldots,x_{d-1}$ $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Yuval Filmus
fonte

Para os negativos, acho que o truque do complemento do 2 pode funcionar.

Complexidade

Não sem um limite superior na magnitude dos coeficientes. Isto é o que minha prova mostra.

Yuval Filmus 13/10

Desculpe eu não tive esta parte "Eu sempre posso responder a sua

consultas

por zero"

d - 1

$d-1$

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

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

Complexidade

Este é um argumento adversário. Seu algoritmo pede à caixa preta o valor de

lugares e sempre responde a zero. Eu mostro que isso não é suficiente para você deduzir o valor de

f

$f$

d - 1

$d-1$

f

$f$

Yuval Filmus 13/10