Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, there are $X \xrightarrow{\phi} R \xrightarrow{\psi} Y$, each map computable in $O(|x|)$ time for each $x \in X$, where $|x|$ is the size of the input (e.g. for integers, $X = \Bbb{Z}$ it’s $|x| \approx \ln (x)$, at least for a subset of integers that will map into $R$ “without trouble”). Let’s work with $k = 1$. Then we need a polynomial $g \in \Bbb{Z}_p[x_1]$ such that $\psi\circ g\circ \phi (x) = f(x)$, for all $x \in X$.

Now, there is a finite set of $x \in X$, say $\{x_i\}$ such that $f(\{x_i\}) = f(X)$, since $\Bbb{Z}_p$ is finite. Well then we want $g(\phi (x_i)) = f^{\leftarrow} (y_i)$, where $y_i = f(x_i)$ and $f^{\leftarrow}$ maps $y_i$ to any of the $\phi(x_i)$ such that $f(x_i) = y_i$. This is doable with the poynomial:

$$g(z) = \sum_{t = 0}^{p-1} f(\phi^{\leftarrow}(z))(1 – (z – t)^{p-1})$$

(which can be computed in $O(p \ln (p))$ time obviously, I digress…)

Now suppose that it’s true for $k = n$ memory slots. Is there an inductive proof to finish this off?

Solutions Collecting From Web of "Any problem computable in $k$ memory slots can be computed with polynomials."

No induction needed.

Define $g_i(z_1, \dots, z_k) = \sum_{(a_1,\dots, a_k) \in X’} \left (f(a_1, \dots, a_k)_i \prod_{j=1}^k (1- (z_j – a_j)^{p-1}) \right )$.

It is computable in time at most $O(p^k k^2 \ln(p))$. When $p = 2$ and $k = 100$, that explains why there are some exponential time algos. But not proven yet. We’d need to prove that there exist sets of such polynomials that aren’t computable in poly time.