In its original XVIII century form the classical Waring problem consisted in finding for each natural $k$ the smallest such $s=g(k)$ that all natural numbers $n$ can be written as sums of $s$ non-negative $k$-th powers, $n=x_1^k+\ldots+x_s^k$. In the XIX century the problem was modified as the quest of finding such minimal $s=G(k)$ that {\it almost all\/} $n$ can be expressed in this form. In the XX century this problem was further specified, as for finding such $G(k)$ {\it and\/} the precise list of exceptions. In the present
talk I sketch the key steps in the solution of this problem, with a special emphasis on algebraic and computational aspects. I describe various connections of this problem, and its modifications, such as the rational Waring problem, the easier Waring problem, etc., with the current research in polynomial computer algebra,
especially with identities, symbolic polynomials, etc. and promote several outstanding computational challenges.