Znajdź wielomian w dwóch lub trzech zapytaniach

Czarna ramka oznacza, że mogę ocenić wielomian w dowolnym punkcie. $f(x)$ $f(x)$

Dane wejściowe : czarne pole wielomianu monicznego stopnia . $f(x) \in\mathbb{Z}^+[x]$ $d$
Wydajność: W współczynniki wielomianu . $d$ $f(x)$

Mój algorytm: 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$

Oszacuj wielomian w wielu punktach za pomocą czarnej skrzynki i uzyskaj układ równań liniowych. Teraz mogę rozwiązać układ równań liniowych, aby uzyskać pożądane współczynniki. $\mathcal{f(x)}$ $d$

Jednak w tym przypadku potrzebuję wielu zapytań do czarnej skrzynki. Chcę zminimalizować liczbę zapytań . Czy istnieje sposób na ograniczenie liczby zapytań do zaledwie dwóch lub trzech? $\mathcal{O(d)}$

algorithms polynomials Złożoność
źródło

Zmieniasz pytanie. Być może powinieneś najpierw zdecydować o swoim pytaniu, a dopiero potem go zadać. W przeciwnym razie może to być nieco frustrujące dla osoby odpowiadającej.

Yuval Filmus

Co oznacza ?

Z^{+}

$\mathbb{Z}^+$

md5

zestaw liczb całkowitych dodatnich

złożoność

BTW dla twojego algorytmu, współczynniki można obliczyć w zamiast z zamkniętą formułą Lagrange'a.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

md5

Dokładnie to samo pytanie brzmi inaczej: math.stackexchange.com/questions/446130/...

Nayuki

Odpowiedzi:

Możesz określić wielomian za pomocą dwóch zapytań. Najpierw zapytaj wielomian przy aby uzyskać górną granicę na wartości współczynników. Teraz wielomian w wybranym przez ciebie i odczytaj współczynniki z podstawowego rozszerzenia . $x=1$ $M$ $x > M$ $x$

Co ciekawe, jeśli pozwolisz, aby współczynniki były ujemne, nie możesz zrobić lepiej niż zapytań. Rzeczywiście, zawsze mogę odpowiedzieć na twoje zapytania przez zero, a to nie naprawia wartości wielomianu, ponieważ wszystkie wielomiany postaci są zgodne z moimi odpowiedziami. $d$ $d-1$ $x_1,\ldots,x_{d-1}$ $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Yuval Filmus
źródło

W przypadku negatywów myślę, że sztuczka dopełniacza 2 może działać.

Złożoność

Nie bez górnej granicy wielkości współczynników. To pokazuje mój dowód.

Yuval Filmus

Niestety nie dostałem tę rolę "zawsze mogę odpowiedzieć na

zapytań

przez zero"

d - 1

$d-1$

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

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

Complexity

To jest argument przeciwnika. Twój algorytm prosi czarną skrzynkę o wartość

w miejscach

i zawsze odpowiada zero. Pokazuję, że to nie wystarczy, aby wywnioskować wartość

f

$f$

d - 1

$d-1$

f

$f$

Yuval Filmus