3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, this notion is trivial. Every nonempty PR language with nonempty complement is PR-complete under primitive recursive reductions. $\endgroup$ Nov 28, 2012 at 13:45

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.)

The phenomenon here is quite general: A class of languages, closed under negation, and with other milder closure properties (like a pairing function) can't contain a universal example.

$\endgroup$
1
  • $\begingroup$ Thank you. I was well aware of the non-existence of universal p.r. functions by the diagonalization argument; I think my confusion here is coming from trying to see PR as a complexity class and attempting to use complexity-preserving reductions to characterize it. $\endgroup$ Nov 28, 2012 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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