# How would one characterize a PR-complete language?

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.

-
Yes, this notion is trivial. Every nonempty PR language with nonempty complement is PR-complete under primitive recursive reductions. –  Emil Jeřábek Nov 28 '12 at 13:45

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.

-
Thank you, I found this quite elucidating. –  Chris Pressey Nov 29 '12 at 11:12
You’re welcome. –  Emil Jeřábek Nov 29 '12 at 12:07
You don't mean the definition of universality that you wrote, because it trivializes the question. The language $\{0\}$ is universal in this sense, because you can reduce any PR language $X$ to it by the PR function that sends $x$ to 0 if $x\in X$ and to 1 otherwise.
Let me therefore switch to a more standard notion of universality: For every PR language $X$ there is an index $e$ such that, for all $x$, we have $x\in X$ iff $(e,x)\in l$. (Here $(e,x)$ refers to your favorite (PR) pairing function.) No PR language $l$ can satisfy this definition because $(x,x)\notin l$ is PR and has no index $e$. (If it had an index $e$ then it would contain $(e,e)$ iff it doesn't contain it.)