6
$\begingroup$

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?

$\endgroup$
  • 9
    $\begingroup$ 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 $\endgroup$ – Mateus de Oliveira Oliveira Dec 9 '12 at 13:31
  • $\begingroup$ @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. $\endgroup$ – Chris Pressey Dec 9 '12 at 16:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Huck Bennett Dec 9 '12 at 16:40
  • 2
    $\begingroup$ @MateusdeOliveiraOliveira maybe you can make this an answer ? $\endgroup$ – Suresh Venkat Dec 9 '12 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Chris Pressey Dec 10 '12 at 12:21
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Chris Pressey Dec 10 '12 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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