Найти многочлен в двух или трех запросах

Черный ящик с $f(x)$ означает, что я могу оценить многочлен в любой точке. $f(x)$

Вход : черный ящик монического полинома степени . $f(x) \in\mathbb{Z}^+[x]$ $d$
Вывод: В коэффициенты многочлена . $d$ $f(x)$

Мой алгоритм: пусть

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$

Оцените полином в многих точках, используя черный ящик, и получите систему линейных уравнений. Теперь я могу решить систему линейных уравнений, чтобы получить нужные коэффициенты. $\mathcal{f(x)}$ $d$

Однако в этом случае мне нужно много запросов к черному ящику. Я хочу минимизировать количество запросов . Есть ли способ уменьшить количество запросов до двух или трех? $\mathcal{O(d)}$

algorithms polynomials сложность
источник

Вы продолжаете менять вопрос. Возможно, вам следует сначала определиться с вопросом и только потом задавать его. В противном случае это может быть несколько неприятно для ответчика.

Юваль

Что означает

Z^{+}

$\mathbb{Z}^+$

md5

набор натуральных чисел

Сложность

Кстати, для вашего алгоритма коэффициенты могут быть вычислены в

вместо

с помощью закрытой формулы Лагранжа.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

md5

Точно такой же вопрос, сформулированный по-другому: math.stackexchange.com/questions/446130/…

Наюки,

Ответы:

Вы можете определить многочлен, используя два запроса. Сначала запросите многочлен при чтобы получить верхнюю границу для значения коэффициентов. Теперь запросите многочлен в по вашему выбору и считайте коэффициенты из базового расширения . $x=1$ $M$ $x > M$ $x$

Любопытно, что если вы позволите коэффициентам быть отрицательными, то вы не сможете сделать лучше, чем запросов. Действительно, я всегда могу ответить на ваши запросы на ноль, и это не фиксирует значение многочлена, так как все многочлены вида соответствуют моим ответам. $d$ $d-1$ $x_1,\ldots,x_{d-1}$ $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Юваль Фильмус
источник

Для негативов я думаю, что трюк с дополнением 2 может сработать.

Сложность

Не без верхней границы величины коэффициентов. Это то, что показывает мое доказательство.

Юваль

Извините, я не получил эту часть «Я всегда могу ответить на ваши

запросы

ноль»

d - 1

$d-1$

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

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

Сложность

Это аргумент противника. Ваш алгоритм запрашивает черный ящик для значения

разрядах, и он всегда отвечает нулю. Я показываю, что этого недостаточно для вывода значения

f

$f$

d - 1

$d-1$

f

$f$

Юваль