17
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ You keep changing the question. Perhaps you should first decide on your question and only then ask it. Otherwise it can be somewhat frustrating for the answerer. $\endgroup$ – Yuval Filmus Oct 13 '17 at 12:40
  • 2
    $\begingroup$ What does $\mathbb{Z}^+$ means? $\endgroup$ – md5 Oct 13 '17 at 12:44
  • 1
    $\begingroup$ set of positive integers $\endgroup$ – Complexity Oct 13 '17 at 12:45
  • 1
    $\begingroup$ BTW for your algorithm, the coefficients can be computed in $O(n^2)$ instead of $O(n^3)$ with Lagrange's closed formula. $\endgroup$ – md5 Oct 13 '17 at 12:49
  • 2
    $\begingroup$ Exact same question, worded differently: math.stackexchange.com/questions/446130/… $\endgroup$ – Nayuki Oct 14 '17 at 0:38
29
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For negatives I think 2's complement kind of trick may work. $\endgroup$ – Complexity Oct 13 '17 at 12:48
  • 4
    $\begingroup$ Not without an upper bound on the magnitude of the coefficients. This is what my proof shows. $\endgroup$ – Yuval Filmus Oct 13 '17 at 12:49
  • $\begingroup$ Sorry I did not get this part " I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero " $\endgroup$ – Complexity Oct 13 '17 at 13:09
  • 6
    $\begingroup$ This is an adversary argument. Your algorithm asks the black box for the value of $f$ at $d-1$ places, and it always answers zero. I show that this is not enough for you to deduce the value of $f$. $\endgroup$ – Yuval Filmus Oct 13 '17 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.