In this paper:
- Michael Ben-Or and Prasoon Tiwari. 1988. A deterministic algorithm for sparse multivariate polynomial interpolation, In: Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC '88). Association for Computing Machinery, New York, NY, USA, pp 301–309. https://doi.org/10.1145/62212.62241
what's given is $P(x)$ a (sparse) multivariate polynomial with real(or complex) coefficients. The author claimed two things.
- It is known that the problem of determining the exact number of monomials in $P(x)$ given by a black-box is #P-Complete (Kaltofen 1986).
- It turns out that one can not determine the number of monomials $t$ in $P(x)$ in time $t^{O(l)}$ (or $t^{O(1)}$, can not see quite clearly).
How to understand these? Is there any proof or reference? Does it mean that it is computationally infeasible to determine the number of monomials in $P(x)$? How will it be if the coefficients are taken from finite fields?
Does it mean that when evaluating at $2t$ points, if the Hankel matrix generated by these points has full rank, it is computationally infeasible to know what the exact number of monomials is?
