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?
Complexity of problems solvable by primitive recursion
cc.complexity theory;computability