Motivation: Computing a problem in $k$ memory slots
Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$?
Thanks... Good luck!
Edit. I think there may be irreducible polys in that ring that are hard to compute. Or something! Something is going on here, peeps.
For simplicity, let's assume that $p = 2$ and we are dealing with input in binary.
Let $F : \{0,1\}^k \to \{0,1\}$ be any boolean function. Define
\begin{align} P(x_0,x_1,\ldots,x_{k-1}) &= \sum_{a \in \{0,1\}^k} F(a_0,a_1,\ldots,a_{k-1})\cdot\prod_{i = 0}^{k}\Big(a_ix_i+(1-a_i)(1-x_i)\Big) \\ &= \sum_{a \in \{0,1\}^k\ :\ F(a) = 1}\ \prod_{i = 0}^{k}\Big(a_ix_i+(1-a_i)(1-x_i)\Big). \end{align}
Observe that $F \equiv P$, so any algorithm calculating $P$ at some input is also an algorithm for $F$ and vice versa. Now, there are $2^{2^k}$ different boolean functions and speaking informally, algorithms have to differ to represent all of them. In other words, there are functions such that for any algorithm there is an input that takes a lot of time to calculate. In fact, Shannon showed that most of them require circuits of size $\frac{2^{k}}{\log k}$, which isn't polynomial. You can find more info on circuit complexity here.
Finally, be aware that there are deep connections between the circuit complexity and the standard time-complexity in terms of Turing machines, but these are nevertheless different concepts.
I hope this helps $\ddot\smile$