I am aware of Lagrange's Four-Square Theorem, which states that every positive integer can be written as the sum of at most four squares. Clearly some integers require fewer squares. Does there exist a polynomial-time algorithm to compute the minimum number of squares needed to sum to a given integer $n$?
It is easy to come up with a dynamic program for this problem; denote the number of squares needed to represent $i$ by $T[i]$, then
\begin{align*} T[i] = \min_{1 \le s \le \sqrt{i}} T[i - s^2] + 1 \end{align*}
Thus, we can solve this problem in $\Theta(n\sqrt{n})$, but this is not polynomial in $\log(n)$.