patternMajor
Find a polynomial in two or three queries
Viewed 0 times
threepolynomialtwofindqueries
Problem
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.
-
Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.
-
Output: The $d$ coefficients of polynomial $f(x)$.
My algorithm: let
$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$
Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.
However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?
-
Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.
-
Output: The $d$ coefficients of polynomial $f(x)$.
My algorithm: let
$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$
Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.
However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?
Solution
You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your choice and read off the coefficients from the base $x$ expansion.
Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.
Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.
Context
StackExchange Computer Science Q#82409, answer score: 31
Revisions (0)
No revisions yet.