The complexity class $PR$ is the set of all formal languages that can be decided by a primitive recursive function. Is there any language $l$ known to be complete for this class, i.e., for every language in $PR$ there is a primitive-recursive reduction from it to $l$?


Perhaps this notion is trivial, or it trivially does not exist (thus it is not worth appearing explicitly in the literature, at least not in this form) and I am simply thinking too hard about it. A reasonable candidate for $l$ would seem to be {<$p,x,y$> | $p$ is an encoding of a p.r. function which maps $x$ to $y$}, but that set would not appear to be itself primitive recursive, as there is no universal p.r. function to accept it.



How would one characterize a PR-complete language?
Let me consider another reformulation of the question which makes it nontrivial: is there a PR-complete language under *polynomial-time* reductions?


The answer is no, since (apart from the first few levels) each level of the Gregorczyk hierarchy is closed under polynomial reductions. Thus, if the alleged complete language were in $\mathcal E\_n$, then it would follow that PR collapses to $\mathcal E\_n$, however the Grzegorczyk hierarchy is known to be strictly increasing. Alternatively, one may use the time-hierarchy theorem: if $L$ were a PR-complete language, then $L$ is decidable in time eventually bounded by $A(k,n)$ for a constant $k$, where $A$ is the Ackermann function. Then every language polynomially reducible to $L$ is decidable in time $A(k,n^c)$, which is asymptotically (much) less than $A(k+1,n)$. By the time hierarchy theorem, there exists a language decidable in time $A(k+1,n)$ (and therefore primitive recursive) which is not polynomially reducible to $L$.


The same argument applies to PR-completeness under reductions whose complexity is restricted to any fixed level of the Gregorczyk hierarchy instead of polynomial time.


