1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 10
    $\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$
    – Emil Jeřábek
    Aug 5 at 11:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.