Subscribe to the weekly news from TrueShelf
Let \(p\) be a polnyomial with natural coefficients. An oracle can evaluate \(p\) at any value you like. Can you determine all the coefficients by making two queries to the oracle?
Note: You are free to have an adaptive strategy, in that the second query can depend on the answer to the first.
Let the polynomial be \(P(x) = \sum_i a_i x^i \). First evaluate \(P(1)\), this would give you \(q=\sum_i a_i\). Now evaluate \(P(q)=\sum_i a_i q^i\), since each \(a_i < q\) the number \(a_n,\dots,a_0\) is a valid base \(q\) number. Hence convert the number \(P(q)\) into base \(q\) format to recover the coefficients. I learned about this trick from a blog post of John D. Cook on the same topic.