I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of problems computable in logarithmic space.

I attach a screenshot from Neil Immerman's book Descriptive Complexity, where I found the result.

enter image description here

enter image description here

Now, this seems very confusing to me, since it is known that the class PR is strictly bigger than L (see, for example, https://en.wikipedia.org/wiki/PR_(complexity) or https://math.stackexchange.com/questions/4170046/are-primitive-recursive-functions-computable-in-logarithmic-space). I imagine the theorem I attach is not talking about PR and L, but about something else. I'd appreciate some help in clarifying this.

  • 11
    $\begingroup$ Logspace is the true logspace. But primitive recursive functions as defined here are much weaker than the usual class of primitive recursive functions, which would correspond to what you would get if A were the infinite structure N, whereas here we only consider finite structures. $\endgroup$ Aug 5, 2022 at 11:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.