<p>See "<em>Complexity  Hierarchies Beyond Elementary</em>" by Schmitz, cf. <a href="http://arxiv.org/abs/1312.5686" rel="nofollow">1312.5686 [cs.CC]</a> at arxiv. </p>

<p>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.</p>

CC BY-SA 3.0
2014-05-21T13:50:28.683Z
2014-05-21T13:50:28.683Z
phs
<p>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$.</p>

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

<p>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:</p>

<p>$i = 0$</p>

<p>$While \, (i + 1 \ne x) \, \, \, \, i++$</p>

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

CC BY-SA 3.0
2014-05-21T17:48:48.983Z
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$?
Jake
CC BY-SA 3.0
2014-05-21T21:21:31.133Z
@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.
GMB
CC BY-SA 3.0
2014-05-21T23:53:47.223Z
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$
Jake
CC BY-SA 3.0
2014-05-21T05:51:43.110Z
2014-05-21T05:51:43.110Z
GMB
<p>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). </p>

<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2014-05-21T23:08:31.537Z
NP is a small subclass of Primitive Recursive. I think this question is more suitable for [cs.se] which has a broader scope.
Kaveh
<cc.complexity-theory><computability>
Complexity of problems solvable by primitive recursion
Jake
# Complexity of problems solvable by primitive recursion

(Asked by: username_0 on 2014-05-21)

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?

**Tags:** cc.complexity-theory, computability
> **Comments:**
> **username_1**: NP is a small subclass of Primitive Recursive. I think this question is more suitable for [cs.se] which has a broader scope.  

---

## 2 answers

### Answer by username_2 on 2014-05-21. Score: 2

See "*Complexity Hierarchies Beyond Elementary*" by Schmitz, cf. [1312.5686 [cs.CC]](http://arxiv.org/abs/1312.5686) 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.


---

### Answer by username_3 on 2014-05-21. Score: 1

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!

> **Comments:**
> **username_0**: 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$?  
> **username_3**: @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.  
> **username_0**: 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$  

---

