I was wondering if there is any known complexity of problem for which primitive recursive functions cannot solve. One such problem might be "is N the ackermann function for $k_1$ $k_2$" as it seems one would need to compute the ackermann function for $k_1$ and $k_2$ to decide this. It also seems that the traveling salesman problem can be solved using a primitive recursive function (I didn't try. it just seems possible by generating all permutations and checking each one). So it seems that I have a very hard problem to solve which can't be solved by primitive recursion and one very hard problem to solve which can be (I think).

So what complexity of problems can be solved by primitive recursion, what complexity of problems cannot? Perhaps NP-hard problems are solvable with primitive recursion but not as efficiently?

edit: It seems that my suspicion "Perhaps NP-hard problems are solvable with primitive recursion but not as efficiently" was correct. If this is the case which problems are solvable as efficiently with a turing machine as with primitive recursion?

  • 1
    $\begingroup$ NP is a small subclass of Primitive Recursive. I think this question is more suitable for Computer Science which has a broader scope. $\endgroup$
    – Kaveh
    May 21 '14 at 23:08

See "Complexity Hierarchies Beyond Elementary" by Schmitz, cf. 1312.5686 [cs.CC] at arxiv.

It deals with complexity beyond elementary, but also beyond primitive recursive (and beyond that too). There you'll find classes and example of complete problems.


The class $PR$ (primitive recursive functions) strictly contains the class $ELEMENTARY = TIME(2^n) \cup TIME(2^{2^n}) \cup TIME(2^{2^{2^n}}) \cup \dots$.

You say "Perhaps NP-hard problems are solvable with primitive recursion but not as efficiently." This is true. Even the total recursive function model of computation does not carry a notion of time complexity that agrees with that of Turing Machines.

To see a simple example, how do you define the predecessor function in primitive recursive terms? You'd have to do something like: use the unbounded search operator to find the smallest $y$ such that $S(y) = x$. That is analogous to computing $f(x) = x-1$ with the function:

$i = 0$

$While \, (i + 1 \ne x) \, \, \, \, i++$

Which takes $2^n$ time. Obviously, there is a better way!

  • $\begingroup$ I'm a bit confused on the predecessor example. If h is the primitive recursion of f ang g then g can just be the projection function $P_i$ which would accomplish the same thing but put the running time in O(1). Also wouldn't that running time of yours be in $n^2$? $\endgroup$
    – Jake
    May 21 '14 at 17:48
  • $\begingroup$ @Jake: I'm not totally sure what you mean by implementing predecessor with the projection function. The while loop does a number of iterations that is linear in the value of $x$, so if $n$ is the length of the bit representation of $x$, then it takes $2^n$ time. $\endgroup$
    – GMB
    May 21 '14 at 21:21
  • $\begingroup$ I assumed n was the value itself not the number of bits in it. I also assumed that you were using the successor constructor style of natural numbers where equality checking takes $n$. I see what you mean now. To clarify what I meant by the projection function see the below defnition pred 0 = <whatever you want, zero has no predecessor> pred n = P_0^0 this is as far as I understand a primitive recursive definition of the predecessor function that takes $n$ $\endgroup$
    – Jake
    May 21 '14 at 23:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.