<p>Transforming the comments above into an answer: </p>

<p>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 ...$$</p>

<p>It can be shown that ELEMENTARY is <a href="http://en.wikipedia.org/wiki/ELEMENTARY">strictly contained in PR</a>. Since $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ we have that $\mathsf{NEXP}$ is strictly contained in $PR$. </p>

<p>As pointed out by Huck Bennett above, the fact that $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$
is a consequence from the fact that </p>

<p>$$\mathsf{NEXP} = \text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}}) \subsetneq \mathsf{ELEMENTARY}$$</p>

CC BY-SA 3.0
2012-12-10T13:10:48.097Z
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.
Chris Pressey
CC BY-SA 3.0
2012-12-09T17:40:23.070Z
2012-12-10T01:16:30.233Z
2012-12-10T01:16:30.233Z
Mateus de Oliveira Oliveira
<p>For the longest time I was under the impression that <strong><a href="http://en.wikipedia.org/wiki/PR_%28complexity%29" rel="nofollow noreferrer">PR</a></strong> contains <strong><a href="http://en.wikipedia.org/wiki/NEXP" rel="nofollow noreferrer">NEXP</a></strong>.  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.</p>

<p>All that I can currently conclude about them is that it's almost certainly not the case that <strong>PR</strong> = <strong>NEXP</strong>, as <a href="https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems">there are known <strong>NEXP</strong>-complete problems</a>, while <a href="https://mathoverflow.net/questions/114770/how-would-one-characterize-a-pr-complete-language">the notion of completeness for <strong>PR</strong> is problematic</a>.</p>

<blockquote>
  <p>What is known about the relationship between <strong>PR</strong> and <strong>NEXP</strong>?</p>
</blockquote>

CC BY-SA 3.0
2012-12-09T13:31:14.790Z
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 http://en.wikipedia.org/wiki/ELEMENTARY
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2012-12-09T16:11:47.073Z
@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.
Chris Pressey
CC BY-SA 3.0
2012-12-09T16:40:20.543Z
@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.
Huck Bennett
CC BY-SA 3.0
2012-12-09T17:21:04.267Z
@MateusdeOliveiraOliveira maybe you can make this an answer ?
Suresh Venkat
CC BY-SA 3.0
2012-12-10T12:21:40.680Z
@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](http://rjlipton.wordpress.com/2009/05/11/simulation-of-nondeterministic-machines/) calls it (or something very close to it) a conjecture.
Chris Pressey
CC BY-SA 3.0
2012-12-11T06:57:45.090Z
@ChrisPressey The straightforward relationship is $NTIME(f(n)) \subseteq DTIME(2^{O(f(n))})$ whenever $f(n) = \Omega(n)$ by, say, executing a BFS on the possible computation tree of the corresponding NTM which contains $O(k^{t(n)}) = 2^{O(t(n))}$ nodes for $k$ smaller than the finite cardinality of the transition function defining the NTM. HuckBennett's bound is rather loose, but sufficient. I believe this is one of the first examples in the time complexity section in Sipser's book. The conjecture in the blog post requires the coefficient of $t(n)$ in the exponent to be arbitrarily small.
Yonatan N
CC BY-SA 3.0
2012-12-11T10:16:22.083Z
Thanks @Yonatan, I got it now.  I think "in general" is what threw me.  It works when $f$ has some substance to it, the open question is how small $f$ can be.
Chris Pressey
CC BY-SA 3.0
2012-12-12T14:50:31.190Z
Yes, Yonatan is right, I should have $NTIME(f(n)) \subseteq DTIME(f(n) \cdot 2^{f(n)})$. Then $f(n) = \Omega(n) \Rightarrow NTIME(f(n)) \subseteq 2^{O(f(n))}$. The conclusion is the same.
Huck Bennett
<cc.complexity-theory>
What is known about the relationship between PR and NEXP?
Chris Pressey
# What is known about the relationship between PR and NEXP?

(Asked by: username_0 on 2012-12-09)

For the longest time I was under the impression that **[PR](http://en.wikipedia.org/wiki/PR_%28complexity%29)** contains **[NEXP](http://en.wikipedia.org/wiki/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](https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems), while [the notion of completeness for **PR** is problematic](https://mathoverflow.net/questions/114770/how-would-one-characterize-a-pr-complete-language).

> What is known about the relationship between **PR** and **NEXP**?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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 http://en.wikipedia.org/wiki/ELEMENTARY  
> **username_0**: @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.  
> **username_2**: @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.  
> **username_3**: @MateusdeOliveiraOliveira maybe you can make this an answer ?  
> **username_0**: @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](http://rjlipton.wordpress.com/2009/05/11/simulation-of-nondeterministic-machines/) calls it (or something very close to it) a conjecture.  
> **username_4**: @ChrisPressey The straightforward relationship is $NTIME(f(n)) \subseteq DTIME(2^{O(f(n))})$ whenever $f(n) = \Omega(n)$ by, say, executing a BFS on the possible computation tree of the corresponding NTM which contains $O(k^{t(n)}) = 2^{O(t(n))}$ nodes for $k$ smaller than the finite cardinality of the transition function defining the NTM. HuckBennett's bound is rather loose, but sufficient. I believe this is one of the first examples in the time complexity section in Sipser's book. The conjecture in the blog post requires the coefficient of $t(n)$ in the exponent to be arbitrarily small.  
> **username_0**: Thanks @Yonatan, I got it now.  I think "in general" is what threw me.  It works when $f$ has some substance to it, the open question is how small $f$ can be.  
> **username_2**: Yes, Yonatan is right, I should have $NTIME(f(n)) \subseteq DTIME(f(n) \cdot 2^{f(n)})$. Then $f(n) = \Omega(n) \Rightarrow NTIME(f(n)) \subseteq 2^{O(f(n))}$. The conclusion is the same.  

---

## 1 answers

### Answer by username_1 on 2012-12-09. Score: 13 | Accepted answer

Transforming the comments above into an answer:

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](http://en.wikipedia.org/wiki/ELEMENTARY). Since $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ we have that $\mathsf{NEXP}$ is strictly contained in $PR$.

As pointed out by username_2 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}$$

> **Comments:**
> **username_0**: Thank you kindly.  I'm still a little fuzzy on username_2'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.  

---

