Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
9  
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 –  Mateus de Oliveira Oliveira Dec 9 '12 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. –  Chris Pressey Dec 9 '12 at 16:11
1  
@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 Dec 9 '12 at 16:40
2  
@MateusdeOliveiraOliveira maybe you can make this an answer ? –  Suresh Venkat Dec 9 '12 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. –  Chris Pressey Dec 10 '12 at 12:21
show 3 more comments

1 Answer

up vote 12 down vote accepted

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. 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}$$

share|improve this answer
    
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 Dec 10 '12 at 13:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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