Are primitive recursive functions computable in logarithmic space?

Question

How can I prove that every primitive recursive function is computable on logarithmic space complex nondeterministic Turing machine?

Any help will be much appreciated!!

Answer 1

The class $\mathsf{PR}$ of primitive recursive functions is gigantic from the perspective of complexity theory. It includes - properly - all the usual complexity classes such as $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{PSPACE}$, $\mathsf{EXPEXPEXPEXPSPACE}$, and so on.

Specifically, we can prove the following. For $p(x_1,...,x_n,y)$ a primitive recursive function, let $\mathsf{Bound}(p)$ be the class of functions computable by some deterministic Turing machine $\varphi$ whose runtime on input $k$ is $\le p(a_1,...,a_n,k)$ for some fixed $a_1,...,a_k$. Then there is a primitive recursive function not in $\mathsf{Bound}(p)$. This is a good exercise; the key tool here is Kleene's $T$-predicate, which is primitive recursive.

By making $p$ sufficiently big we can show that $\mathsf{PR}\not\subseteq\mathsf{C}$ for a wide range of complexity classes $\mathsf{C}$. For example, take $\mathsf{C}$ to be nondeterministic linear space. The naive "space-to-time" and "nondeterministic-to-deterministic" translations are each exponential, and so we get $\mathsf{C}\subseteq$ $\mathsf{EXPEXPTIME}$. Now let $p(x_1,x_2,x_3,y)=x_1^{x_2^y}+x_3$. Applying the above result gives a primitive recursive function not in $\mathsf{EXPEXPTIME}$, hence not in $\mathsf{C}$.

In fact, it should be a bit surprising that there are any naturally-occurring recursive functions which are not primitive recursive.