# What is known about the relationship between PR and NEXP?

For the longest time I was under the impression that PR contains NEXP. Try as I might, I am unable to recall where I picked up this notion. I've looked recently, but I have not been able to find anything about what is known about their relationship.

All that I can currently conclude about them is that it's almost certainly not the case that PR = NEXP, as there are known NEXP-complete problems, while the notion of completeness for PR is problematic.

What is known about the relationship between PR and NEXP?

• I think NEXP is strictly contained in PR. I might be missing something but, $ELEMENTARY = DTIME(2^n)\cup DTIME(2^{2^n}) \cup DTIME(2^{2^{2^n}}) \cup ...$. It is known that ELEMENTARY is strictly contained in PR. And $NEXP\subseteq ELEMENTARY$. Thus NEXP is strictly contained in PR. See en.wikipedia.org/wiki/ELEMENTARY Commented Dec 9, 2012 at 13:31
• @Mateus, do you have a reference or proof for $NEXP\subseteq ELEMENTARY$? The wikipedia article you link to doesn't seem to claim that -- it only claims $EXP\subsetneq ELEMENTARY$. Perhaps it is possible to easily derive the former from the latter, but I'm not confident enough of my understanding of $NEXP$ to say. Commented Dec 9, 2012 at 16:11
• @Chris: In general $NTIME(f(n)) \subseteq DTIME(2^{f(n)})$, so $NEXP = NTIME(2^{poly(n)}) \subseteq DTIME(2^{2^{2^n}}) \subsetneq ELEMENTARY$ as Mateus said. Commented Dec 9, 2012 at 16:40
• @MateusdeOliveiraOliveira maybe you can make this an answer ? Commented Dec 9, 2012 at 17:21
• @Huck: could I trouble you for a reference or proof sketch of that NTIME-DTIME relationship? That does sound familiar (Papadimitriou's book?) but I may be confusing it with Savitch's Theorem. I thought such a basic relationship would be mentioned in the zoo, but doesn't seem to be. Also, this 2009 blog post calls it (or something very close to it) a conjecture. Commented Dec 10, 2012 at 12:21

NEXP is strictly contained in PR. Indeed define the class ELEMENTARY as $$\mathsf{ELEMENTARY}=\text{DTIME}(2^n)\cup \text{DTIME}(2^{2^n}) \cup \text{DTIME}(2^{2^{2n}}) \cup ...$$
It can be shown that ELEMENTARY is strictly contained in PR. Since $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ we have that $\mathsf{NEXP}$ is strictly contained in $PR$.
As pointed out by Huck Bennett above, the fact that $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ is a consequence from the fact that
$$\mathsf{NEXP} = \text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}}) \subsetneq \mathsf{ELEMENTARY}$$
• Thank you kindly. I'm still a little fuzzy on Huck Bennett's assertion, but I've convinced myself that the specific relationship $\text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}})$ holds. Commented Dec 10, 2012 at 13:10