Ciro Santilli @cirosantilli  40

And when it can't, attempt to classify which subset of the integers can be reached. E.g. Legendre's three-square theorem.

Compared to Waring's problem, this is potentially much harder, as we can go infinitely negative in our attempts, there isn't a bound on how many tries we can have for each number.

In other words, it is unlikely to have a Conjecture reduction to a halting problem.

math.stackexchange.com/questions/2382011/computational-complexity-of-modular-exponentiation-from-rosens-discrete-mathem mentions:can be calculated in:Remember that $log(m)$ and $log(n)$ are the lengths in bits of $m$ and $n$, so in terms of the length in bits $M$ and $N$ we'd get:

A theorem that is not very important on its own, often an intermediate step to proving something that the author feels deserves the name "theorem".